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

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()


dp0 = list2d(N+1, S+1, 0)

dp1 = list2d(N+1, S+1, 0)

dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    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 j+a <= S:
            
            dp1[i+1][j+a] += dp0[i][j] * (i+1)
            
            dp2[i+1][j+a] += dp1[i][j] * (N-i)
            dp1[i+1][j+a] += dp1[i][j] 
            dp2[i+1][j+a] += dp0[i][j] * (i+1) * (N-i)
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)

Solution (Python):
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

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


dp = [np.zeros(S + 10, dtype=np.int64) for _ in range(N+1)]



ans = 0
for i in range(N):
    a = A[i]

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

    
    dp[i + 1][a:] += dp[i][:-a]
    dp[i + 1] %= MOD

    
    ans += dp[i + 1][S]
    ans %= MOD

print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

dp0 = [0] * (S+1)
dp1 = [0] * (S+1)
dp2 = [0] * (S+1)
nxt0 = [0] * (S+1)
nxt1 = [0] * (S+1)
nxt2 = [0] * (S+1)
dp0[0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        
        nxt0[j] += dp0[j]
        nxt1[j] += dp0[j] + dp1[j]
        nxt2[j] += dp0[j] + dp1[j] + dp2[j]
        
        if j+a <= S:
            nxt1[j+a] += dp0[j] + dp1[j]
            nxt2[j+a] += dp0[j] + dp1[j]
        nxt0[j] %= MOD
        nxt1[j] %= MOD
        nxt2[j] %= MOD
    dp0 = nxt0[:]
    dp1 = nxt1[:]
    dp2 = nxt2[:]
    nxt0 = [0] * (S+1)
    nxt1 = [0] * (S+1)
    nxt2 = [0] * (S+1)
ans = dp2[S]
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()


dp0 = list2d(N+1, S+1, 0)

dp1 = list2d(N+1, S+1, 0)

dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()


dp0 = list2d(N+1, S+1, 0)

dp1 = list2d(N+1, S+1, 0)

dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()


dp0 = list2d(N+1, S+1, 0)

dp1 = list2d(N+1, S+1, 0)

dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)

Solution (Python):
import numpy as np

n,s = map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353

res = 0
dp = np.zeros(s + 1, dtype = int)

for i in range(n):
    dp[0] += 1
    dp[a[i]:] += dp[:-a[i]].copy()
    dp %= mod
    res += dp[s]
    res %= mod

print(res)

Solution (Python):
import numpy as np

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

ans = 0
dp = np.zeros(S + 1, dtype=np.int64)

for a in A:
    dp[0] += 1
    dp[a:] += dp[: -a].copy()
    dp %= MOD
    ans += dp[S]

print(ans % MOD)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))



n,s = LI()
a = LI()
ans = 0
dp = [[0]*(s+1) for _ in range(n)]
dp[0][0] = 1
if s >= a[0]:
    dp[0][a[0]] = 1
for i in range(1,n):
    b = a[i]
    for j in range(s+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] + 1
        else:
            dp[i][j] = dp[i-1][j]
    for j in range(s+1):
        if dp[i-1][j]:
            if j + b <= s:
                if j == 0:
                    dp[i][j+b] += dp[i][j]
                    dp[i][j+b] %= mod
                else:
                    dp[i][j+b] += dp[i-1][j]
                    dp[i][j+b] %= mod
for i in dp:
    ans += i[-1]
    ans %= mod
print(ans)

Solution (Python):
from sys import stdin
mod = 998244353
def solveAsPolynomial():
    import numpy as np
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    ans = 0
    f = np.zeros(S+1,np.int64)
    for A in a:
        
        f[0] += 1
        f[A:] += f[:-A].copy()
        f %= mod
        ans += f[S]
        
        ans %= mod
    return ans
def main():
  ans = solveAsPolynomial()
  print(ans)
if __name__ =="__main__":
  main()

Solution (Python):
from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [0]*(S+1)
    ans = 0
    for A in a:
        dp[0] += 1
        for i in reversed(range(A,S+1)):
            dp[i] += dp[i-A]    
            dp[i] %= mod
        ans += dp[S]
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [0]*(S+1)
    ans = 0
    for A in a:
        dp[0] += 1
        for i in reversed(range(A,S+1)):
            dp[i] += dp[i-A]    
            dp[i] %= mod
        ans += dp[S]
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md = 998244353
    n, s = MI()
    aa = LI()
    dp = [0] * (s + 1)
    ans = 0
    for a in aa:
        dp[0] += 1
        for i in range(s, a - 1, -1):dp[i] += dp[i - a]
        ans += dp[s]
    print(ans%md)

main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md = 998244353
    n, s = MI()
    aa = LI()
    dp = [0] * (s + 1)
    ans = 0
    for a in aa:
        dp[0] += 1
        for i in range(s, a - 1, -1):
            dp[i] += dp[i - a]
            dp[i] %= md
        ans += dp[s]
        ans %= md
    print(ans)

main()

Solution (Python):
import numpy as np

n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = np.zeros((s + 1, 3), dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()

    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)

Solution (Python):
n,s = map(int,input().split())
a = tuple(map(int,input().split()))

mod = 998244353

dp = [[0]* (s+1) for _ in range(n+1)]

for i in range(1,n+1):
    a_t = a[i-1]
    for j in range(s+1):
        dp[i][j] = dp[i-1][j]
        if(j == 0)|(j == a_t):
            dp[i][j] += 1
        if(j >= a_t):
            dp[i][j] += dp[i-1][j-a_t]
        dp[i][j] %= mod

ans = 0
for i in range(n+1):
    ans = (ans + dp[i][-1]) % mod
print(ans)

Solution (Python):
N, S = map(int, input().split())
a = list(map(int, input().split()))

dp1 = [0] * (S + 1)
ans = 0
for i in range(N):
  dp1[0] += 1
  dp2 = [0] * (S + 1)
  for j in range(S+1):
    dp2[j] += dp1[j]
    if j + a[i] <= S:
      dp2[j+a[i]] += dp1[j]
  dp1 = dp2[:]
  ans += dp1[-1]
  ans = ans % 998244353
print(ans)

Solution (Python):
import numpy as np

n, s = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = np.array([[0] * 3 for _ in range(s + 1)], dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()
    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)

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

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

for i, a in enumerate(A):
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    if a <= S:
        dp[a] += (i + 1)
    ans += dp[S]

print(ans % MOD)

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    n,s = map(int,input().split())
    a = tuple(map(int,input().split()))

    mod = 998244353

    res = 0

    
    dp = [[0]*3003 for i in range(n)]

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

if __name__ == "__main__":
    main()

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

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

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

for i in range(1, N+1):
    a = A[i-1]
    dp1[i][0] = 1
    for j in range(S+1):
        dp1[i][j] += dp1[i-1][j]
        if j == a:
            dp1[i][j] += 1
        if j-a >= 0:
            dp1[i][j] += dp1[i-1][j-a]
        dp1[i][j] %= mod
    r += dp1[i][S]
print(r%mod)

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

for i in range(1, N+1):
    a = A[i-1]
    dp1[i][0] = 1
    for j in range(S+1):
        dp1[i][j] += dp1[i-1][j]
        dp2[i][j] = dp2[i-1][j]
        if j == a:
            dp1[i][j] += 1
        if j-a >= 0:
            dp1[i][j] += dp1[i-1][j-a]
        dp2[i][j] += dp1[i][j]
        dp1[i][j] %= mod
        dp2[i][j] %= mod

print(dp2[-1][S])

Solution (Python):
K = 32
P = 998244353
pa = (1 << 30) - ((1 << 30) % P)
M = []
N, S = map(int, input().split())
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = 1 << K * S
mmm = (1 << K) - 1
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += mm
    s += s >> a * K
    s -= ((s & m) >> 30) * pa
    ans += s & mmm

print(ans % P)

Solution (Python):
K = 32
P = 998244353
pa = (1 << 30) - ((1 << 30) % P)
M = []
N, S = map(int, input().split())
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = (1 << K * (S + 1)) - 1
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += s >> S * K

print(ans % P)

Solution (Python):
def f_knapsack_for_all_segments(MOD=998244353):
    
    import numpy as np
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    ans = 0
    f = np.zeros(S + 1, np.int64)  
    for a in A:
        
        f[0] += 1  
        f[a:] += f[:-a].copy()  
        f %= MOD
        
        ans += f[S]
        ans %= MOD
    return ans

print(f_knapsack_for_all_segments())

Solution (Python):
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * 3001, 2)
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += (s >> S * K) & mmm

print(ans % P)

Solution (Python):
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * 3001, 2)
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += (s >> S * K) & mmm

print(ans % P)

Solution (Python):
def setM():
    k = K2 // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m, ~m, (1 << K2 + k) % P))
        k //= 2
        break

def modp(n):
    for k, m, tm, a in M:
        n = (n & tm) + ((n & m) >> K2 + k) * a
    return n

K = 64
K2 = K // 2
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Solution (Python):
def setM():
    k = K2 // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m, ~m, (1 << K2 + k) % P))
        k //= 2

def modp(n):
    for k, m, tm, a in M:
        n = (n & tm) + ((n & m) >> K2 + k) * a
    return n

K = 64
K2 = K // 2
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Solution (Python):
mod = 998244353

n,s = map(int, input().split())
a = list(map(int, input().split()))
m = 3000
DP = [0]*(m+1)
ans = 0
for ai in a:
    DP[0] += 1
    for j in reversed(range(ai,m+1)):
        DP[j] += DP[j-ai]
        DP[j] %= mod
    ans += DP[s]
    ans %= mod
print(ans)

Solution (Python):
def setM():
    K2 = K // 2
    k = K // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m))
        k //= 2

def modp(n):
    K2 = K // 2
    k = K // 2
    for k, m in M:
        n = (n & (~m)) + ((n & m) >> (K2 + k)) * ((1 << K2 + k) % P)
    return n

K = 64
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Solution (Python):
def setM():
    K2 = K // 2
    k = K // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m))
        k //= 2

def modp(n):
    K2 = K // 2
    k = K // 2
    for k, m in M:
        n = (n & (~m)) + ((n & m) >> (K2 + k)) * ((1 << K2 + k) % P)
    return n

K = 64
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    ans = 0
    dp = [0]*(s+1)
    for i in range(n):
        ai = a[i]
        for j in range(s+1)[::-1]:
            nj = j+ai
            if nj > s:
                continue
            dp[nj] += dp[j]
            dp[nj] %= mod
        if ai <= s:
            dp[ai] += i+1
            dp[ai] %= mod
        ans += dp[s]
        ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
ans = 0
P = 998244353
for i, a in enumerate(A):
    X[0] += 1
    for j in range(S, a-1, -1):
        X[j] = (X[j] + X[j-a]) % P
    ans += X[S]
print(ans % P)

Solution (Python):

import sys
input = sys.stdin.readline
MOD = 998244353

n, s = map(int, input().split())
a = [int(item) for item in input().split()]

dp = [[0] * (s+1) for _ in range(n)]
dp[0][0] = 1
if a[0] <= s:
    dp[0][a[0]] = 1
ans = 0
for i, item in enumerate(a[1:]):
    for j in range(s+1):
        
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        
        if j + item <= s:
            dp[i+1][j + item] += dp[i][j]
            dp[i+1][j + item] %= MOD
    
    if item <= s:
        dp[i+1][item] += 1
    dp[i+1][0] += 1
    ans += dp[i+1][s]
    ans %= MOD

print(ans)

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    ans = 0
    f = [0]*(s+1)
    f[0] = 0
    for i in a:
        f[0] += 1
        for j in range(s+1)[::-1]:
            nj = j+i
            if nj > s:
                continue
            f[nj] += f[j]
            f[nj] %= mod
        ans += f[s]
        ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
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(S):

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

    ans += ndp[S]
    ans %= mod

    dp = ndp

    

    
print (ans)

Solution (Python):
from numpy import*
(n,s),a,m,e=map(int,input().split()),list(map(int,input().split())),998244353,3001;D=zeros((n,e));D[0][a[0]]=1
for j,i in enumerate(a[1:]):D[j+1,i]+=j+2;D[j+1,i:]+=D[j,:e-i];D[j+1,:]=(D[j+1,:]+D[j,:])%m
print(int(sum(D[:, s]) % m))

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

dp1 = [0]*(3001*N)
dp2 = [0]*(3001*N)

for n in range(N):
    for s in range(3000,-1,-1):
        dp2[n*N+s] = dp2[(n-1)*N+s]
        dp1[n*N+s] = dp1[(n-1)*N+s]
        if s>A[n]:
            dp2[n*N+s] += dp1[(n-1)*N+s-A[n]]*(N-n)
            dp1[n*N+s] += dp1[(n-1)*N+s-A[n]]
        elif s==A[n]:
            dp2[n*N+s] += (n+1)*(N-n)
            dp1[n*N+s] += n+1
        dp2[n*N+s] %= mod
        dp1[n*N+s] %= mod

print(dp2[(N-1)*N+S])

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]


mod = 998244353
inf = 1e10


def solve():
    n, s = LI()
    a = LI()
    dp1 = [0] * (3000 + 1)
    dp2 = [0] * (3000 + 1)
    ans = 0

    for i in range(n):
        for j in range(s+1):
            dp2[j] = dp1[j]
        
        for j in range(a[i], s + 1):
            dp2[j] += dp1[j - a[i]]
            dp2[j] %= mod
        dp2[a[i]] += i + 1 
        ans += dp2[s]
        ans %= mod
        dp1 = dp2[::1]
        
    print(ans)
            
    return



if __name__ == '__main__':
    solve()

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

dp = [0 for i in range(s+1)]

ans = 0
tmp = [0]

for i, ai in enumerate(a):
    dpn = []
    dp[0] = i + 1
    for j in range(s+1):
        if j - ai >= 0 and dp[j-ai]:
            dpn.append((dp[j] + dp[j-ai]) % mod)
        else:
            dpn.append(dp[j])
    
    ans = (ans + dpn[s]) % mod
    dp = dpn[:]
print(ans)

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

dp = [0] * (s+1)
ans = 0
for i in range(n):
    ndp = dp[:]
    if a[i] <= s:
        ndp[a[i]] = (ndp[a[i]] + i+1) % mod
    for j in range(s):
        if j+a[i] <= s:
            ndp[j+a[i]] = (ndp[j+a[i]] + dp[j]) % mod
    ans = (ans + ndp[s]) % mod
    dp = ndp[:]
print(ans)

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

dp = [0] * (S+1)
ans = 0
for i in range(N):
    ndp = dp[:]
    if A[i] <= S:
        ndp[A[i]] = (ndp[A[i]] + i+1) % mod
    for j in range(S):
        if j+A[i] <= S:
            ndp[j+A[i]] = (ndp[j+A[i]] + dp[j]) % mod
    ans = (ans + ndp[S]) % mod
    dp = ndp[:]
print (ans)

Solution (Python):
n,s=map(int,input().split())
t=[0]*(s+1)
m=998244353
a=list(map(int,input().split()))
ans=0
for i in range(n):
    d=t.copy()
    if a[i]<=s:
        for j in range(a[i],s+1):
            t[j]+=d[j-a[i]]
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np
MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
F = np.zeros(s+1, dtype=np.int64)
ans = 0
for a in A:
  F[0] += 1
  F[a:] += F[:-a].copy()
  F %= MOD
  ans += F[s]
  ans %= MOD
print(ans)

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

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

    dp = [[0] * (S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(S+1):
            dp[i+1][j] = (dp[i+1][j] + dp[i][j])%mod
            if j+a <= S:
                tmp = 1
                if j == 0:
                    tmp *= (i+1)
                if j+a == S:
                    tmp *= (N-i)
                dp[i+1][j+a] = (dp[i+1][j+a] + (dp[i][j] * tmp)%mod)%mod
    print(dp[-1][S])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(3001)]
dp[0] = 1
ans = 0
for i in range(n):
	for j in range(s, a[i]-1, -1):
		dp[j] += dp[j-a[i]]
		dp[j] %= MOD
	dp[a[i]] += i
	dp[a[i]] %= MOD
	ans += dp[s]
	ans %= MOD
print(ans)

Solution (Python):
def main():
    mod=998244353
    n,s=map(int,input().split())
    A=tuple(map(int,input().split()))
    DP=[[x+1]+[0]*s for x in range(n+1)]
    for i,a in enumerate(A):
        for j in range(1,s+1):
            if j-a<0:
                DP[i+1][j]=DP[i][j]
            else:
                DP[i+1][j]=DP[i][j]+DP[i][j-a]
            DP[i+1][j]%=mod
    ans=0
    for dp in DP:
        ans+=dp[-1]
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
B=[[0]*(s+1) for _ in range(n+1)]
ans=0
for i in range(n):
  a=A[i]
  if a<s:
    B[i+1][a]+=i+1
  elif a==s:
    B[i+1][a]+=(i+1)*(n-i)
  for j in range(s+1):
    if j<=s:
      B[i+1][j]+=B[i][j]
    if 0<=j-a and j<s:
      B[i+1][j]+=B[i][j-a]
    if 0<=j-a and j==s:
      B[i+1][j]+=B[i][j-a]*(n-i)
    B[i+1][j]%=mod
print(B[n][s])

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

d = [[0 for _ in range(2)] for _ in range(s+1)]
mod = 998244353

for i in range(n):
    for j in reversed(range(s-a[i]+1)):
        d[j + a[i]][0] += d[j][0]
        d[j + a[i]][1] += d[j][0] * (n - i)
        d[j + a[i]][0] %= mod
        d[j + a[i]][1] %= mod
    if a[i] <= s:
        d[a[i]][0] += i + 1
        d[a[i]][1] += (i + 1) * (n - i)
        d[a[i]][0] %= mod
        d[a[i]][0] %= mod

print(d[s][1])

Solution (Python):
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,s = nm()
a = nl()
mod = 998244353
ans = 0
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i,v in enumerate(a):
    dp[i+1][0] = 1
    for j in range(s+1):
        dp[i+1][j] += dp[i][j]
        if j >= v: dp[i+1][j] += dp[i][j-v]
        dp[i+1][j] %= mod
    ans += dp[i+1][s]
print(ans%mod)