Problem:


Score : 600 points

Problem Statement

Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.

For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:

f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq S \leq 3000

1 \leq A_i \leq 3000

Input

Input is given from Standard Input in the following format:

N S
A_1 A_2 ... A_N

Output

Print the sum of f(L, R), modulo 998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

5

The value of f(L, R) for each pair is as follows, for a total of 5.

f(1,1) = 0

f(1,2) = 1 (for the sequence (1, 2))

f(1,3) = 2 (for (1, 2) and (3))

f(2,2) = 0

f(2,3) = 1 (for (3))

f(3,3) = 1 (for (3))

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

152



Sample input:
3 4
2 2 4


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))

    dp0 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp1 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp2 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp0[0][0] += 1
    for i in range(N):
        a = A[i]
        dp0i = dp0[i]
        dp1i = dp1[i]
        dp2i = dp2[i]
        dp0n = dp0[i+1]
        dp1n = dp1[i+1]
        dp2n = dp2[i+1]
        for j in range(S+1):
            dp0ij = dp0i[j]
            dp1ij = dp1i[j]
            dp0n[j] += dp0ij
            dp1n[j] += dp1ij
            dp2n[j] += dp2i[j]

            if j+a > S: continue
            dp1nja = dp1n[j+a]
            dp2nja = dp2n[j+a]
            dp1nja += dp0ij * (i+1)
            dp2nja += dp0ij * (i+1) * (N-i)
            dp1nja += dp1ij
            dp2nja += dp1ij * (N-i)
    print(dp2[N][S])

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))

    dp0 = [[Mint() for _ in range(S+3001)] for _ in range(N+1)]
    dp1 = [[Mint() for _ in range(S+3001)] for _ in range(N+1)]
    dp2 = [[Mint() for _ in range(S+3001)] for _ in range(N+1)]
    dp0[0][0] += 1
    for i in range(N):
        a = A[i]
        dp0i = dp0[i]
        dp1i = dp1[i]
        dp2i = dp2[i]
        dp0n = dp0[i+1]
        dp1n = dp1[i+1]
        dp2n = dp2[i+1]
        for j in range(S+1):
            dp0ij = dp0i[j]
            dp1ij = dp1i[j]
            dp1nja = dp1n[j+a]
            dp2nja = dp2n[j+a]

            dp0n[j] += dp0ij
            dp1nja += dp0ij * (i+1)
            dp2nja += dp0ij * (i+1) * (N-i)

            dp1n[j] += dp1ij
            dp1nja += dp1ij
            dp2nja += dp1ij * (N-i)

            dp2n[j] += dp2i[j]
    print(dp2[N][S])

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11139418

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, x in enumerate(a):
        for j in range(S + 1):
            # 選択しない
            prev = dp[i][j]
            curr = dp[i + 1][j]

            curr[0] = (curr[0] + prev[0]) % MOD
            curr[1] = (curr[1] + prev[0] + prev[1]) % MOD
            curr[2] = (curr[2] + prev[0] + prev[1] + prev[2]) % MOD

            # 選択する
            if j - x < 0: continue
            prev_x = dp[i][j - x]

            curr[1] = (curr[1] + prev_x[0] + prev_x[1]) % MOD
            curr[2] = (curr[2] + prev_x[0] + prev_x[1]) % MOD

    ret = dp[N][S][2]
    print(ret)


if __name__ == '__main__':
    main()

# 0: 開始していないが開始して選択することができる
# 1: 開始しており選択を選べる
# 2: 閉じており選択できない

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 998244353

    dp = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(S+1):
            dp[i+1][j][0] = (dp[i+1][j][0] + dp[i][j][0]) % MOD
            dp[i+1][j][1] = (dp[i+1][j][1] + dp[i][j][1]) % MOD
            dp[i+1][j][2] = (dp[i+1][j][2] + dp[i][j][2]) % MOD

            if j+a > S: continue
            dp[i+1][j+a][1] = (dp[i+1][j+a][1] + dp[i][j][1] + (dp[i][j][0] * (i+1))) % MOD
            dp[i+1][j+a][2] = (dp[i+1][j+a][2] + (dp[i][j][1] * (N-i)) + (dp[i][j][0] * (i+1) * (N-i))) % MOD

    print(dp[N][S][2])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11139418

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, x in enumerate(a):
        for j in range(S + 1):
            # 選択しない
            prev = dp[i][j]

            dp[i + 1][j][0] = (dp[i + 1][j][0] + prev[0]) % MOD
            dp[i + 1][j][1] = (dp[i + 1][j][1] + prev[0] + prev[1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + prev[0] + prev[1] + prev[2]) % MOD

            # 選択する
            if j - x < 0: continue
            prev_x = dp[i][j - x]

            dp[i + 1][j][1] = (dp[i + 1][j][1] + prev_x[0] + prev_x[1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + prev_x[0] + prev_x[1]) % MOD

    ret = dp[N][S][2]
    print(ret)


if __name__ == '__main__':
    main()

# 0: 開始していないが開始して選択することができる
# 1: 開始しており選択を選べる
# 2: 閉じており選択できない

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11139418

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1

    for i, x in enumerate(a):
        for j in range(S + 1):
            # 選択しない
            dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][0] + dp[i][j][1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][j][0] + dp[i][j][1] + dp[i][j][2]) % MOD

            # 選択する
            pj = j - x
            if pj < 0: continue
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][pj][0] + dp[i][pj][1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][pj][0] + dp[i][pj][1]) % MOD

    ret = dp[N][S][2]
    print(ret)


if __name__ == '__main__':
    main()

# 0: 開始していないが開始して選択することができる
# 1: 開始しており選択を選べる
# 2: 閉じており選択できない

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 998244353

    dp = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0]
            if dp[i+1][j][0] >= MOD: dp[i+1][j][0] -= MOD

            dp[i+1][j][1] += dp[i][j][1]
            if dp[i+1][j][1] >= MOD: dp[i+1][j][1] -= MOD

            dp[i+1][j][2] += dp[i][j][2]
            if dp[i+1][j][2] >= MOD: dp[i+1][j][2] -= MOD

            if j+a > S: continue
            dp[i+1][j+a][1] += (dp[i][j][0] * (i+1)) % MOD
            if dp[i+1][j+a][1] >= MOD: dp[i+1][j+a][1] -= MOD
            dp[i+1][j+a][2] += (dp[i][j][0] * (i+1) * (N-i)) % MOD
            if dp[i+1][j+a][2] >= MOD: dp[i+1][j+a][2] -= MOD
            dp[i+1][j+a][1] += dp[i][j][1]
            if dp[i+1][j+a][1] >= MOD: dp[i+1][j+a][1] -= MOD
            dp[i+1][j+a][2] += (dp[i][j][1] * (N-i)) % MOD
            if dp[i+1][j+a][2] >= MOD: dp[i+1][j+a][2] -= MOD

    print(dp[N][S][2])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))
    MOD = 998244353

    dp = [[[0 for _ in range(3)] for _ in range(S+3001)] for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0]
            if dp[i+1][j][0] >= MOD: dp[i+1][j][0] -= MOD
            dp[i+1][j+a][1] += (dp[i][j][0] * (i+1)) % MOD
            if dp[i+1][j+a][1] >= MOD: dp[i+1][j+a][1] -= MOD
            dp[i+1][j+a][2] += (dp[i][j][0] * (i+1) * (N-i)) % MOD
            if dp[i+1][j+a][2] >= MOD: dp[i+1][j+a][2] -= MOD

            dp[i+1][j][1] += dp[i][j][1]
            if dp[i+1][j][1] >= MOD: dp[i+1][j][1] -= MOD
            dp[i+1][j+a][1] += dp[i][j][1]
            if dp[i+1][j+a][1] >= MOD: dp[i+1][j+a][1] -= MOD
            dp[i+1][j+a][2] += (dp[i][j][1] * (N-i)) % MOD
            if dp[i+1][j+a][2] >= MOD: dp[i+1][j+a][2] -= MOD

            dp[i+1][j][2] += dp[i][j][2]
            if dp[i+1][j][2] >= MOD: dp[i+1][j][2] -= MOD
    print(dp[N][S][2])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))

    dp = [[[Mint() for _ in range(3)] for _ in range(S+3001)] for _ in range(N+1)]
    dp[0][0][0] += 1
    for i in range(N):
        a = A[i]
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0]
            dp[i+1][j+a][1] += dp[i][j][0] * (i+1)
            dp[i+1][j+a][2] += dp[i][j][0] * (i+1) * (N-i)

            dp[i+1][j][1] += dp[i][j][1]
            dp[i+1][j+a][1] += dp[i][j][1]
            dp[i+1][j+a][2] += dp[i][j][1] * (N-i)

            dp[i+1][j][2] += dp[i][j][2]
    print(dp[N][S][2])

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
MOD = 998244353
A = list(map(int, input().split()))

# dp[i][s] : Rをiに固定した時に、和がsとなる整数列の組が何回現れるか
dp = [[0]*(S+1) for i in range(N+1)]
ans = 0

for i, a in enumerate(A, 1):
  for s in range(S+1):
    dp[i][s] = dp[i-1][s]
    dp[i][s] += s==0 or s==a
    if s >= a:
      dp[i][s] = (dp[i][s] + dp[i-1][s-a]) % MOD
  ans = (ans + dp[i][-1]) % MOD # R=i, L=1,2,...i(=R)のf(L, R)を加算

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, list(input().split())))

ans = 0
dp = [[0]*(S+1) for _ in range(N+1)]
for i in range(N):
    dp[i][0] += 1       # Lがiからを足す
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]             # A[i]を選ばない
        dp[i+1][j] %= MOD
        if j+A[i]<=S:
            dp[i+1][j+A[i]] += dp[i][j]    # A[i]を選ぶ
            dp[i+1][j+A[i]] %= MOD
    ans += dp[i+1][S]    # Rがiまでを足す
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, list(input().split())))

ans = 0
dp = [0]*(S+1)
for i in range(N):
    dp[0] += 1      # Lがiからを足す
    next_dp = [0]*(S+1)
    for j in range(S+1):
        next_dp[j] += dp[j]             # A[i]を選ばない
        next_dp[j] %= MOD
        if j+A[i]<=S:
            next_dp[j+A[i]] += dp[j]    # A[i]を選ぶ
            next_dp[j] %= MOD
    dp = next_dp
    ans += dp[S]    # Rがiまでを足す
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
x = [0]
x.extend([int(x) for x in input().split()])
 
# 状態リストを作成
m = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
m[0][0][0] = 1
 
for i in range(1,N+1):
    
    for k in range(S+1):

        # x を含めない
        m[i][k][0] += m[i-1][k][0] # まだ開始しない
        m[i][k][1] += m[i-1][k][0] + m[i-1][k][1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
        m[i][k][2] += m[i-1][k][0] + m[i-1][k][1] + m[i-1][k][2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

        # x を含める場合
        if k - x[i] >= 0:
            m[i][k][1] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
            m[i][k][2] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
        
        m[i][k][0] = m[i][k][0] % 998244353
        m[i][k][1] = m[i][k][1] % 998244353
        m[i][k][2] = m[i][k][2] % 998244353
            
print(m[N][S][2])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
  if A[n] < S:
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
  dt %= 998244353
print(dt[N,S] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = [[0 for _ in range(S+1)] for x in range(N+1)]

for n in range(1, N+1):
  if A[n] <= S:
    dt[n][A[n]] += n
  for i in range(1,S+1):
    step = dt[n-1][i] * 2 - dt[n-2][i]
    if (i + A[n]) <= S:
      dt[n][i+A[n]] += step - dt[n-1][i]
    dt[n][i] += step

print(dt[N][S] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = [[0 for _ in range(S+1)] for x in range(N+1)]

for n in range(1, N+1):
  if A[n] <= S:
    dt[n][A[n]] += n
  for i in range(1,S+1):
    if (i + A[n]) <= S:
      dt[n][i+A[n]] += dt[n-1][i] - dt[n-2][i]
    dt[n][i] += dt[n-1][i] + (dt[n-1][i] - dt[n-2][i])

print(dt[N][S] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = np.array(list(map(int, input().split())))

total = 0
comb = np.zeros(N)
comb_idx = 0

while comb_idx < 2**N:
  tmp = bin(comb_idx)[2:]
  comb[-len(tmp):] = np.array(list(map(int, list(tmp))))
  if np.dot(A, comb) == S:
    R = 1
    while True:
      if tmp[-R] == "1":
        break
      else:
        R += 1
    total += (N-len(tmp)+1) * R
    comb_idx += 1
  else:
    comb_idx += 1
print(total % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys

sys.setrecursionlimit(10**5)

def solve(nums, s):
    @lru_cache(None)
    def dfs(i, k):
        if k < 0:
            return []
        if k == 0:
            return [i-1]
        if i >= n:
            return []
        if k == s:
            return dfs(i+1, k-nums[i])
        return dfs(i+1, k-nums[i]) + dfs(i+1, k)

    ans = 0
    n = len(nums)
    for i in range(n):
        for e in dfs(i, s):
            ans = (ans + (i+1)*(n-e)) % 998244353
    return ans


def main():
    n, s = map(int, input().split())
    nums = [int(c) for c in input().split()]
    print(solve(nums, s))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

M = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
prev = Counter()
for i, a in enumerate(A, 1):
  curr = Counter({a+s: c for s, c in prev.items() if a+s<=S})
  curr.update({a:i})
  ans = (ans + curr[S]*(N-i+1))%M
  curr.update(prev)
  prev = curr

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import itertools
A = [0]
N, S = list(map(int, input().split()))
A = A + list(map(int, input().split()))
val = 0
for L in range(1, N+1):
  for R in range(L, N+1):
    A_ = A[L:R+1]
    lists = []
    for n in range(len(A_)):
      for comb in itertools.combinations(A_, n+1):
        lists.append(list(comb))
    for lis in lists:
      _sum = sum(lis)
      if _sum == S:
        val += 1
      if val == 998244353:
        val = 0
print(val)

Submission status: Time Limit Exceeded

Solution code:
def main():
  mod = 998244353

  dp = [[[0]*3 for i in range(3030)] for j in range(3030)];

  n,k = map(int,input().split())
  a = list(map(int,input().split()))
  dp[0][0][0] = 1;
  for i in range(n):
      for j in range(k+1):
        dp[i+1][j][0] = (dp[i+1][j][0] + dp[i][j][0]) % mod
        dp[i+1][j][1] = (dp[i+1][j][1] + dp[i][j][0] + dp[i][j][1]) % mod
        dp[i+1][j][2] = (dp[i+1][j][2] + dp[i][j][0] + dp[i][j][1] + dp[i][j][2]) % mod
        if j + a[i] <= k:
          dp[i+1][j+a[i]][1] = (dp[i+1][j+a[i]][1] + dp[i][j][0] + dp[i][j][1]) % mod
          dp[i+1][j+a[i]][2] = (dp[i+1][j+a[i]][2] + dp[i][j][0] + dp[i][j][1]) % mod
            
        
    
  print(dp[n][k][2])
  
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for _ in range(S+1)] for _ in range(N)]

for i in range(0, S+1):
    if i == A[0]:
        dp[0][i] = 1

for i in range(1, N):
    for j in range(0, S+1):
        if j > A[i]:
            dp[i][j] = (dp[i-1][j]+dp[i-1][j-A[i]])%mod
        elif j == A[i]:
            dp[i][j] = (dp[i-1][j]+(i+1))%mod
        else:
            dp[i][j] = dp[i-1][j]
            
ans = 0
for i in range(0, N):
    ans = (ans+dp[i][S])%mod

print (ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for _ in range(S+1)] for _ in range(N)]

for i in range(0, S+1):
    if i == A[0]:
        dp[0][i] = 1

for i in range(0, N):
    for j in range(0, S+1):
        if j > A[i]:
            dp[i][j] = (dp[i-1][j]+dp[i-1][j-A[i]])%mod
        elif j == A[i]:
            dp[i][j] = (dp[i-1][j]+(i+1))%mod
        else:
            dp[i][j] = dp[i-1][j]
            
ans = 0
for i in range(0, N):
    ans = (ans+dp[i][S])%mod

print (ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
MOD = 998244353  # type: int

def solve(N: int, S: int, A: "List[int]"):
    dp = [[0]*(S+1) for _ in range(N+1)]

    for i in range(N):
        for s in range(S+1):
            if s >= A[i]:
                dp[i+1][s] = dp[i][s]+dp[i][s-A[i]]+int(A[i]==s or s==0)
            else:
                dp[i+1][s] = dp[i][s]+int(A[i]==s or s==0)
            dp[i+1][s]%=MOD
    
    answer = 0
    for i in range(N):
        answer += dp[i+1][S]
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
ans = 0
idx = []


def count(s, e):
    return (s + 1) * (N - e) % mod

from itertools import combinations

A = {i: j for i, j in enumerate(A)}
for k in range(1, N + 1):
    for l in map(dict, combinations(A.items(), k)):
        if sum(l.values()) == S:
            li = list(l.keys())
            ans = (ans + count(min(li), max(li))) % mod
                   
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[[0]*2 for _ in range(s)] for _ in range(n)]
mod = 998244353
if a[0] <= s:
    dp[0][a[0]-1][0] = 1
    dp[0][a[0]-1][1] = 1

for i in range(1,n):
    for j in range(s):
        if a[i] < j+1:
            dp[i][j][0] = dp[i-1][j-a[i]][0] + dp[i-1][j][0] 
            dp[i][j][1] = dp[i-1][j-a[i]][0] + dp[i-1][j][0] + dp[i-1][j][1]
        elif a[i] == j+1:
            dp[i][j][0] = dp[i-1][j][0] + i + 1
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1] + i + 1
        else:
            dp[i][j][0] = dp[i-1][j][0]
            dp[i][j][1] = dp[i-1][j][0] + dp[i-1][j][1]
        dp[i][j][0] %= mod   
        dp[i][j][1] %= mod
        
print(dp[n-1][s-1][1])

Submission status: Time Limit Exceeded

Solution code:
N,S =map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
q=[0]*(S+1)
for i in range(N):
    q[0]+=1
    q2=[0]*(S+1)
    for j in range(S+1):
        q[j]%=mod
        q2[j]+=q[j]
        if (j + A[i]) <= S:
            q2[j+A[i]]+=q[j]
    q = q2
    ans+=q[S]
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
dp=[0]*(s+1)
for i in range(n):
	dp[0]+=1
	if a[i]>s:
		continue
	ans+=dp[s-a[i]]*(n-i)
	ans%=mod
	for j in range(s,a[i]-1,-1):
		dp[j]+=dp[j-a[i]]
		dp[j]%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class FastModuloTransform():
    def __init__(self, omega, n, mod):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega, mod - 2, mod)

    def _bit_reverse_(self, d):
        n = len(d)
        ns = n >> 1
        nss = ns >> 1
        ns1 = ns + 1
        i = 0
        for j in range(0, ns, 2):
            if j < i:
                d[i], d[j] = d[j], d[i]
                d[i + ns1], d[j + ns1] = d[j + ns1], d[i + ns1]
            d[i + 1], d[j + ns] = d[j + ns], d[i + 1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d

    def _fmt_(self, A, base):
        halfpow = pow(base, self.n // 2, self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base, n, self.mod)
            wk = 1
            for j in range(m):
                for i in range(j, self.n, 2 * m):
                    U = A[i]
                    V = (A[i + m] * wk) % self.mod
                    A[i] = (U + V) % self.mod
                    A[i + m] = (U + V * halfpow) % self.mod
                wk = (wk * w) % self.mod
            m <<= 1
        return A

    def fmt(self, f):
        A = f + [0] * (self.n - len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A, self.omega)
        return F

    def ifmt(self, F):
        A = F + [0] * (self.n - len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n, self.mod - 2, self.mod)
        f = [(e * nrev) % self.mod for e in self._fmt_(A, self.rev)]
        return f

    def convolute(self, f, g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s * t) % self.mod for s, t in zip(F, G)]
        h = self.ifmt(H)
        return h

fmt = FastModuloTransform(299814, 2**13, 998244353)

MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

F = [0]
res = 0

for i in range(N):
    F[0] += 1
    f = [0 for _ in range(A[i] + 1)]
    f[0] = 1
    f[-1] = 1
    F = fmt.convolute(F, f)
    F = F[:S + 1]
    res += F[S]
    res %= MOD

print(res)

Submission status: Time Limit Exceeded

Solution code:
N,S =map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
q=[0]*(S+1)
for i in range(N):
    q[0]+=1
    q2=[0]*(S+1)
    for j in range(S+1):
        q[j]%=mod
        q2[j]+=q[j]
        if (j + A[i]) <= S:
            q2[j+A[i]]+=q[j]
    q = q2
    ans+=q[S]%mod
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]
        one = dp[i][j][1]
        two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one

answer = dp[N][S][2] % MOD
print(answer)
# 11

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0] % MOD
        one = dp[i][j][1] % MOD
        two = dp[i][j][2] % MOD
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one

answer = dp[N][S][2] % MOD
print(answer)
# 11