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: Wrong Answer

Solution code:
n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[[0 for k in range(2)] for i in range(s+1)] for j in range(n+1)]
mod = 998244353
dp[0][0][0] = 1
for i in range(1,n+1):
  x = a[i-1]
  for j in range(1,s+1):
    if j == x:
      dp[i][j][0] += i
      dp[i][j][1] += i
    if j>x:
      dif = dp[i-1][j-x][0]
      dp[i][j][0] = dif
      dp[i][j][1] = dif*(n+1-i)
    dp[i][j][1] = (dp[i][j][1]+dp[i-1][j][1])%mod
    dp[i][j][0] = (dp[i][j][0]+dp[i-1][j][0])%mod
print(dp[n][s][1])

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    DP = [[0] * (S + 1) for _ in range(N)]
    DP[0][0] = 1
    if A[0] <= S: DP[0][A[0]] = 1
    mod = 998244353
    for i in range(1, N):
        a = A[i]
        for s in range(S):
            if DP[i-1][s] > 0:
                DP[i][s] += DP[i-1][s]
                DP[i][s] %= mod
                if s + a <= S:
                    DP[i][s+a] += DP[i-1][s]
                    DP[i][s+a] %= mod
    Ans = 0
    for i in range(N):
        for j in range(i, N):
            out = (i + 1) * (N - j) % mod 
            if i == j: left = S - A[i]
            else: left = S - A[i] - A[j]
            #print(i, j, out, left)
            if left < 0: continue
            elif left == 0:
                Ans += out 
                Ans %= mod
            else:
                if j > i: inside = (DP[j - 1][left] - DP[i][left] + mod) % mod
                else: inside = 0
                Ans += (inside * out) % mod
                Ans %= mod
    print(Ans)
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, s = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353

ans = 0
B = [0] * (s+1)
for i in range(n):
    for j in range(s, -1, -1):
        if j-A[i] >= 0:
            B[j] += B[j-A[i]]
    if A[i] < len(B):
        B[A[i]] += i+1
    ans += B[s]#*(n-i)
    # B[s] = 0
    # print(B)
print(ans)

Submission status: Wrong Answer

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))

dp = [[1 if _2 == 0 else 0 for _2 in range(s + 1)] for _1 in range(n+1)]

for i, ai in enumerate(a):
  for j, v in enumerate(dp[i]):
    dp[i + 1][j] += v
    if j + ai <= s:
      dp[i + 1][j + ai] += v

print(sum(dp_i[s] for dp_i in dp))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
NS = input().split()
As=input().split()
N=int(NS[0])
S=int(NS[0])
As=[int(x) for x in As]
from itertools import combinations
LRs=list(combinations(range(N),2))
res=0
for i in LRs:
    if i[1]==N-1:
        if i[0]==0:
            LR=As[:]
        else:
            LR=As[i[0]:]
    else:
        if i[0]==0:
            LR=As[:i[1]+1]
        else:
            LR=As[i[0]:i[1]+1]
    for x in range(len(As)):
        xs=[1 for y in list(combinations(LR,x)) if sum(y)==S]
        res+=len(xs)
print(res%998244353)

Submission status: Wrong Answer

Solution code:
N, S = input().split(" ")
N, S = int(N), int(S)
_list = []
for _ in range(0, N):
    _list.append(input)

print(S)

Submission status: Wrong Answer

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353

dp = [0] * (3000 + 1)
dp[0] = 1
ans = 0
for i in range(n):
    for w in range(3000 + 1)[::-1]:
        # 選ぶとき
        if w - a[i] > 0:
            dp[w] += dp[w - a[i]]
        if w - a[i] == 0:
            dp[w] += dp[w - a[i]] * (i + 1)
        dp[w] %= MOD
    ans += dp[s]
print(ans)

Submission status: Wrong Answer

Solution code:
n, s = map(int,input().split())
alist = list(map(int, input().split()))
kago=[]
for i in range(s):
    kago.append([])

answer=0
for i in range(n):
    now=alist[i]
    for k in range(n):
        j=s-k-1
        if j-now>=0:
            kago[j]+=kago[j-now]
    if now-1<len(kago):
        kago[now-1].append(i)
    for kg in kago[-1]:
        answer+=(kg+1)*(n-i)
    kago[-1]=[]
    
    """
    for kg in kago:
        print(kg)
    
    print(answer)
    """
    #print()
    
print(answer)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 998244353

N, S, *As = map(int, read().split())

U = 3010
answer = 0
f = np.zeros(U, np.int64)
for A in As:
    f[0] += 1
    f[A:] += f[:-A]
    f %= MOD
    answer += f[S]

answer %= MOD
print(answer)

Submission status: Wrong Answer

Solution code:

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

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

total_comb = 0

for left_start in range(N):
    dp = [0] * (S+1)
    dp[0] = 1
    for j in range(left_start, N):
        v = A[j]
        for i in range(S, -1, -1):
            if i - v >= 0:
                dp[i] += dp[i-v]
        total_comb += dp[S]
    # print(dp)

print(total_comb)

Submission status: Wrong Answer

Solution code:

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

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

"""
dpなのはそうだろう
普通に行けば、ナップサックdpでいける
S以下のみしか保持しなくていい

始点を保持してしまうと、Sになった時に…？
始点より左にあるやつの個数の和を記録しておけばいい！

連続してなくていいから
"""

dp = [0] * (S+1)
ans = 0
mod = 998244353

for i in range(N):

    ndp = []
    for ll in dp:
        ndp.append(ll)

    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod

    for j in range(N):

        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod

    ans += ndp[S] * (N-i)
    ans %= mod

    dp = ndp
    dp[S] = 0

    #print (dp)

    
print (ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
omega = pow(3,119,mod)
rev_omega = pow(omega,mod-2,mod)

N = 2*10**5
g1 = [1]*(N+1) # 元テーブル
g2 = [1]*(N+1) #逆元テーブル
inv = [1]*(N+1) #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1[i]=( ( g1[i-1] * i ) % mod )
    inv[i]=( ( -inv[mod % i] * (mod//i) ) % mod )
    g2[i]=( (g2[i-1] * inv[i]) % mod )
inv[0]=0

def _ntt(f,L,reverse=False):
    F=[f[i] for i in range(L)]
    n = L.bit_length() - 1
    base = omega
    if reverse:
        base = rev_omega

    if not n:
        return F

    size = 2**n
    wj = pow(base,2**22,mod)
    res = [0]*2**n

    for i in range(n,0,-1):
        use_omega = pow(base,2**(22+i-n),mod)
        res = [0]*2**n
        size //= 2
        w = 1
        for j in range(0,L//2,size):
            for a in range(size):
                res[a+j] = (F[a+2*j] + w * F[a+size+2*j]) % mod
                t = (w * wj) % mod
                res[L//2+a+j] = (F[a+2*j] + t * F[a+size+2*j]) % mod
            w = (w * use_omega) % mod
        F = res

    return res

def ntt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    F = _ntt(f,L)
    return F

def intt(f,L=0):
    l = len(f)
    if not L:
        L = 1<<((l-1).bit_length())
    while len(f)<L:
        f.append(0)
    f=f[:L]
    F = _ntt(f,L,reverse=True)
    inv = pow(L,mod-2,mod)
    for i in range(L):
        F[i] *= inv
        F[i] %= mod
    return F

def convolve(f,g,limit):
    l = len(f)+len(g)-1
    L = 1<<((l-1).bit_length())

    F = ntt(f,L)
    G = ntt(g,L)

    H = [(F[i] * G[i]) % mod for i in range(L)]

    h = intt(H,L)

    return h[:limit]

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

prod = [0]
res = 0
for i in range(N):
    poly = [0 for i in range(A[i]+1)]
    poly[-1] = 1
    poly[0] = 1
    prod[0] = (prod[0] + 1) % mod
    prod = convolve(prod,poly,S+1)
    if len(prod)==S+1:
        res += prod[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

cnt = 0
for l in range(n):
  for r in range(l,n):
    a2 = a[l:r+1]
    for i in range(2**len(a2)):
      t = 0
      for j in range(len(a2)):
        if ((i >> j) & 1):
          t += a2[j]
      if t == s:
        cnt += 1

print(cnt % mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [defaultdict(int) for _ in range(S)]
    ans = 0
    for right in range(N):
        num = A[right]
        if num > S:
            continue
        elif num == S:
            ans = (ans + (right+1) * (N-right)) % MOD
            continue
        for left in dp[S-num]:
            cnt = dp[S-num][left]
            ans = (ans + (left+1) * (N-right) * cnt) % MOD
        for i in range(S-num-1, -1, -1):
            for left in dp[i]:
                dp[i+num][left] += dp[i][left]
        dp[num][right] = 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

def main():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 998244353
    
    dp0 = [[0]*(s+1) for _ in range(n+1)]
    dp1 = [[0]*(s+1) for _ in range(n+1)]
    dp2 = [[0]*(s+1) for _ in range(n+1)]
    dp0[0][0] = 1
    
    for i in range(n):
        for j in range(s+1):
            dp0[i+1][j] += dp0[i][j]
            dp1[i+1][j] += dp1[i][j]
            dp2[i+1][j] += dp2[i][j]
            
            
            if a[i]+j <= s:
                dp1[i+1][j+a[i]] += dp0[i][j] * (i+1)
                dp2[i+1][j+a[i]] += dp0[i][j] * (i+1) * (n-i)
                
                dp1[i+1][j+a[i]] += dp1[i][j]
                dp2[i+1][j+a[i]] += dp1[i][j] * (n-i)
                
            dp0[i+1][j] %= mod
            dp1[i+1][j] %= mod
            dp2[i+1][j] %= mod
                
    print(dp2[n][s])
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache(maxsize=None)
def count(i, s, forced=True):
    global n, a
    if s == 0:
        return i + 1
    elif i == 0:
        return 0
    else:
        return ((count(i - 1, s, False) if not forced else 0) + (count(i - 1, s - a[i], False) if a[i] <= s else 0)) % M

print(sum(count(i, s) * (n - i + 1) % M for i in range(1, n + 1)) % M)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache(maxsize=None)
def count(i, s, hasL, hasR):
    global n, a
    if i == 0:
        return s == 0 and hasL
    else:
        return (
            count(i - 1, s, hasL, hasR)
            + (count(i - 1, s - a[i], False, True) * (n - i + 1) % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * (n - i + 1) % M * i % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * i % M if hasR and not hasL and a[i] <= s else 0)
            + (count(i - 1, s - a[i], False, True) if hasR and not hasL and a[i] <= s else 0)            
        ) % M

for i in range(n + 1):
    for ss in range(s + 1):
        count(i, ss, False, False)
        count(i, ss, False, True)
        count(i, ss, True, True)

print(count(n, s, False, False))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache(maxsize=None)
def count(i, s, hasL, hasR):
    global n, a
    if i == 0:
        return s == 0 and hasL
    else:
        return (
            count(i - 1, s, hasL, hasR)
            + (count(i - 1, s - a[i], False, True) * (n - i + 1) % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * (n - i + 1) % M * i % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * i % M if hasR and not hasL and a[i] <= s else 0)
            + (count(i - 1, s - a[i], False, True) if hasR and not hasL and a[i] <= s else 0)            
        ) % M

print(count(n, s, False, False))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache
def count(i, s, hasL, hasR):
    global n, a
    if i == 0:
        return s == 0 and hasL
    else:
        return (
            count(i - 1, s, hasL, hasR)
            + (count(i - 1, s - a[i], False, True) * (n - i + 1) % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * (n - i + 1) % M * i % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * i % M if hasR and not hasL and a[i] <= s else 0)
            + (count(i - 1, s - a[i], False, True) if hasR and not hasL and a[i] <= s else 0)            
        ) % M

print(count(n, s, False, False))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache
def count(i, s, hasL, hasR):
    global n, a
    if i == 0:
        return s == 0 and hasL
    else:
        return sum([
            count(i - 1, s, hasL, hasR),
            count(i - 1, s - a[i], False, True) * (n - i + 1) % M if not hasR and a[i] <= s else 0,
            count(i - 1, s - a[i], True, True) * (n - i + 1) % M * i % M if not hasR and a[i] <= s else 0,
            count(i - 1, s - a[i], True, True) * i % M if hasR and not hasL and a[i] <= s else 0,
            count(i - 1, s - a[i], False, True) if hasR and not hasL and a[i] <= s else 0            
        ]) % M

print(count(n, s, False, False))

Submission status: Time Limit Exceeded

Solution code:
# https://drken1215.hatenablog.com/entry/2020/03/22/224200

def main():
    import sys
    input = sys.stdin.readline

    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, a in enumerate(A, start=1):
        for j in range(S + 1):
            bf = dp[i - 1][j]
            not_opened = bf[0]
            opened = bf[1]
            closed = bf[2]

            curr = dp[i][j]

            curr[0] = (curr[0] + not_opened) % MOD
            curr[1] = (curr[1] + opened) % MOD
            curr[2] = (curr[2] + closed) % MOD

            if (nj := j + a) <= S:
                dp[i][nj][1] = (dp[i][nj][1] + not_opened * i + opened) % MOD
                dp[i][nj][2] = (dp[i][nj][2] + not_opened * i * (N - i + 1) + opened * (N - i + 1)) % MOD

    ans = dp[-1][-1][2]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://drken1215.hatenablog.com/entry/2020/03/22/224200

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, a in enumerate(A, start=1):
        for j in range(S + 1):
            not_opened = dp[i - 1][j][0]
            opened = dp[i - 1][j][1]
            closed = dp[i - 1][j][2]

            dp[i][j][0] = (dp[i][j][0] + not_opened) % MOD
            dp[i][j][1] = (dp[i][j][1] + opened) % MOD
            dp[i][j][2] = (dp[i][j][2] + closed) % MOD

            if (nj := j + a) <= S:
                dp[i][nj][1] = (dp[i][nj][1] + not_opened * i + opened) % MOD
                dp[i][nj][2] = (dp[i][nj][2] + not_opened * i * (N - i + 1) + opened * (N - i + 1)) % MOD

    ans = dp[-1][-1][2]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://drken1215.hatenablog.com/entry/2020/03/22/224200

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, a 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][1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][j][2]) % MOD
            if (nj := j + a) <= S:
                dp[i + 1][nj][1] = (dp[i + 1][nj][1] + dp[i][j][0] * (i + 1)) % MOD
                dp[i + 1][nj][2] = (dp[i + 1][nj][2] + dp[i][j][0] * (i + 1) * (N - i)) % MOD
                dp[i + 1][nj][1] = (dp[i + 1][nj][1] + dp[i][j][1]) % MOD
                dp[i + 1][nj][2] = (dp[i + 1][nj][2] + dp[i][j][1] * (N - i)) % MOD
    ans = dp[-1][-1][2]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N, S = map(int, input().split())
A = list(map(int, input().split()))
P = 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):
    for s in range(S+1):
        a = A[i]
        dp[i+1][s][0] = dp[i][s][0]
        dp[i+1][s][1] = (dp[i+1][s][1] + dp[i][s][0] + dp[i][s][1]) % P
        dp[i+1][s][2] = (dp[i+1][s][2] + dp[i][s][0] + dp[i][s][1] + dp[i][s][2]) % P
        if s+a <= S:
            dp[i+1][s+a][1] = (dp[i][s][0] + dp[i][s][1]) % P
            dp[i+1][s+a][2] = (dp[i][s][0] + dp[i][s][1]) % P

ans = dp[N][S][2]
print(ans%P)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
P = 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):
    for s in range(S+1):
        a = A[i]
        dp[i+1][s][0] = dp[i][s][0]
        dp[i+1][s][1] = (dp[i+1][s][1] + dp[i][s][0] + dp[i][s][1]) % P
        dp[i+1][s][2] = (dp[i+1][s][2] + dp[i][s][0] + dp[i][s][1] + dp[i][s][2]) % P
        if s+a <= S:
            dp[i+1][s+a][1] = (dp[i][s][0] + dp[i][s][1]) % P
            dp[i+1][s+a][2] = (dp[i][s][0] + dp[i][s][1]) % P

ans = dp[N][S][2]
print(ans%P)

Submission status: Time Limit Exceeded

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

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

for i in range(1,N+1):
  for j in range(S+1):
    dp[i][j][0]=dp[i-1][j][0]
    dp[i][j][1]=dp[i][j][0]+dp[i-1][j][1]
    dp[i][j][2]=dp[i][j][1]+dp[i-1][j][2]
    if j-alist[i-1]>=0:
      tmp=dp[i-1][j-alist[i-1]][0]+dp[i-1][j-alist[i-1]][1]
      dp[i][j][1]+=tmp
      dp[i][j][2]+=tmp
      
    dp[i][j][1]%=MOD
    dp[i][j][2]%=MOD
      
#print(dp)
print(dp[N][S][2])

Submission status: Time Limit Exceeded

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

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

for i in range(1,N+1):
  for j in range(S+1):
    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][2]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]
    if j-alist[i-1]>=0:
      dp[i][j][1]+=dp[i-1][j-alist[i-1]][0]+dp[i-1][j-alist[i-1]][1]
      dp[i][j][2]+=dp[i-1][j-alist[i-1]][0]+dp[i-1][j-alist[i-1]][1]
      
    for k in range(3):
      dp[i][j][k]%=MOD
      
#print(dp)
print(dp[N][S][2])

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353
def resolve():
    # 多項式 解
    N, S = map(int, input().split())
    A = list(map(int, input().split()))

    q = [0]*(S+1)
    ans = 0
    for i in range(N):
        q[0] += 1
        q2 = [0]*(S+1)
        for j in range(S+1):
            # q *= (1 + x^A[i])
            q2[j] += q[j]
            if j + A[i] <= S:
                q2[j + A[i]] += q[j]
                q2[j + A[i]] %= MOD
        q = q2
        ans += q[S]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
MOD = 998244353
def main():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    A = [0] + A
    dp = [[[0] * 3 for __ in range(S + 5)] for _ in range(N + 5)]
    dp[0][0][0] = 1
    for i in range(1, N + 1):
        for s in range(S + 1):
            ps = s - A[i]
            # 0->0
            dp[i][s][0] = (dp[i][s][0] + dp[i - 1][s][0]) % MOD

            # 0->1
            dp[i][s][1] = (dp[i][s][1] + dp[i - 1][s][0]) % MOD
            if ps >= 0:
                dp[i][s][1] = (dp[i][s][1] + dp[i - 1][ps][0]) % MOD

            # 1->1
            dp[i][s][1] = (dp[i][s][1] + dp[i - 1][s][1]) % MOD
            if ps >= 0:
                dp[i][s][1] = (dp[i][s][1] + dp[i - 1][ps][1]) % MOD

            # 0->2
            dp[i][s][2] = (dp[i][s][2] + dp[i - 1][s][0]) % MOD
            if ps >= 0:
                dp[i][s][2] = (dp[i][s][2] + dp[i - 1][ps][0]) % MOD

            # 1->2
            dp[i][s][2] = (dp[i][s][2] + dp[i - 1][s][1]) % MOD
            if ps >= 0:
                dp[i][s][2] = (dp[i][s][2] + dp[i - 1][ps][1]) % MOD

            # 2->2
            dp[i][s][2] = (dp[i][s][2] + dp[i - 1][s][2]) % MOD
    print(dp[N][S][2])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, S = map(int, rl().split())
    A = list(map(int, rl().split()))
    MOD = 998244353
    
    dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S + 1):
            dp[i + 1][j][0] += dp[i][j][0]
            dp[i + 1][j][0] %= MOD
            dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1]
            dp[i + 1][j][1] %= MOD
            dp[i + 1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
            dp[i + 1][j][2] %= MOD
            if j + A[i] <= S:
                dp[i + 1][j + A[i]][1] += dp[i][j][0] + dp[i][j][1]
                dp[i + 1][j + A[i]][1] %= MOD
                dp[i + 1][j + A[i]][2] += dp[i][j][0] + dp[i][j][1]
                dp[i + 1][j + A[i]][2] %= MOD
    print(dp[N][S][2])


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
mod = 998244353
A = list(map(int, input().split()))
D = {0: [[-1, -1]], S: []}
for i in range(N):
    L = [[j, D[j]] for j in D]
    L.sort(reverse=True)
    for jn, j in enumerate(L):
        if j[0]+A[i] <= S:
            for kn, k in enumerate(j[1]):
                if j[0]+A[i] in D:
                    D[j[0]+A[i]].append([(j[0]>0)*k[0]+(j[0]==0)*i, i])
                else:
                    D[j[0]+A[i]] = [[(j[0]>0)*k[0]+(j[0]==0)*i, i]]
p = 0
for i in D[S]:
    p += (i[0] + 1) * (N - i[1]) % mod
    p %= mod
print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    MOD = 998244353

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

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

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

            dp[i+1][j][2] += dp[i][j][2]

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


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    MOD = 998244353

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

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

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

            dp[i+1][j][2] += dp[i][j][2]

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

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


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline


def solve():
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    MOD = 998244353

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

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

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

            dp[i+1][j][2] += dp[i][j][2]

            dp[i+1][j][0] %= MOD
            dp[i+1][j+A[i]][1] %= MOD
            dp[i+1][j+A[i]][2] %= MOD
            dp[i+1][j][1] %= MOD
            dp[i+1][j+A[i]][1] %= MOD
            dp[i+1][j+A[i]][2] %= MOD
            dp[i+1][j][2] %= MOD

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


if __name__ == "__main__":
    solve()

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()