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):
n, s = map(int, input().split())
*A, = map(int, input().split())
p = 998244353
DP = [[0 for j in range(s + 1)] for i in range(n + 1)]
for i in range(1, n + 1):
    for j in range(s + 1):
        DP[i][j] += DP[i - 1][j]
        if j >= A[i - 1]:
            DP[i][j] += DP[i - 1][j - A[i - 1]]
        if j == A[i - 1] or j == 0:
            DP[i][j] += 1
        DP[i][j] %= p
ans = 0
for i in range(1, n + 1):
    ans += DP[i][s]
    ans %= p
print(ans)

Solution (Python):
import sys
from functools import lru_cache
 

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
mod= 998244353
f=[[] for i in range(n+1)]
for k in range(1,n+1):
  if k==1:
    res=[0]*(s+1)
    res[0]=1
    if a[0]<s+1:
      res[a[0]]=1
    f[1]=res
    continue
  res=f[k-1][:]
  k-=1
  for i in range(s,-1,-1):
    if i-a[k]>=0:
      res[i]+=res[i-a[k]]
      res[i]%=mod
  if a[k]<s+1:
      res[a[k]]+=1
  res[0]+=1
  f[k+1]=res
ans=0

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

Solution (Python):
MOD = 998244353
n, s = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
dp = [0] * (s + 1)
dp[0] = 1
for x in a:
    for j in range(s, x - 1, -1):
        dp[j] += dp[j - x]
        if dp[j] >= MOD:
            dp[j] -= MOD
    ans += dp[s]
    dp[0] += 1
print(ans % MOD)

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

lst = [0 for i in range(s+1)]
dp = [lst]
for i in range(n):
    new = [0 for i in range(s+1)]
    new[0] = 1
    if a[i]<=s: new[a[i]] = 1
    for j in range(s+1):
        if j-a[i] >= 0:
            new[j] += dp[-1][j] + dp[-1][j-a[i]]
            new[j] %= mod
        else:
            new[j] += dp[-1][j]
            new[j] %= mod
    dp.append(new)

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

Solution (Python):
def main():
    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

    MOD = 998244353

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

    
    for i, a in enumerate(A):            
        for j in range(S+1):
            if j == a:
                dp[i+1][j] += dp[i][j] + i + 1
                dp[i+1][j] %= MOD
            elif j > a:
                dp[i+1][j] += dp[i][j] + dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= MOD

            
    ans = sum([dp[i][S] for i in range(N+1)])
    ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):



MOD = 998244353

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


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

for i in range(n):
  dp[i + 1][0] = 1
  if A[i] <= s:
     dp[i + 1][A[i]] = 1
  for j in range(s + 1):
    dp[i + 1][j] += dp[i][j] 
    dp[i + 1][j] %= MOD
    if j + A[i] <= s:
      dp[i + 1][j + A[i]] += dp[i][j]
      dp[i + 1][j + A[i]] %= MOD

print(sum(i[-1] for i in dp) % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 18

import numpy as np
def main():
    N,S = map(int,input().split())
    A = list(map(int,input().split()))
    
    before = np.zeros(S + 1,np.int64)
    before[0] = 1
    ans = 0
    for a in A:
        now = np.zeros(S + 1,np.int64)
        now += before
        now[a:] += before[:-a]
        ans += now[S]
        ans %= MOD
        now[0] += 1
        now = np.mod(now,MOD)
        before = now
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 998244353
INF = 10 ** 15

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

    before = [0] * (1 + S)
    before[0] = 1
    ans = 0
    for a in A:
        now = [0] * (1 + S)
        for i in range(S + 1):
            now[i] += before[i]
            if i + a <= S:
                now[i + a] += before[i]
                now[i + a] %= MOD
        now[0] += 1
        ans += now[S]
        ans %= MOD
        before = now
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def S(): return sys.stdin.readline().rstrip()

N,S = map(int,S().split())
A = [0] + LI()
mod = 998244353







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

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

ans = 0
for i in range(1,N+1):
    ans = (ans + dp[i][S]) % mod

print(ans)

Solution (Python):
import numpy as np

n, s = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

U = 3010
count = 0
F = np.zeros(U + 1, np.int64)
for a in A:
    F[0] += 1
    F[a:] += F[:-a].copy()
    F %= MOD
    count += F[s]

count %= MOD
print(count)

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

dp = [0] * (S + 1)
ans = 0
for a in A:
    dp[0] += 1
    for s in range(S + 1)[::-1]:
        if a + s <= S:
            dp[a + s] = (dp[a + s] + dp[s]) % MOD
    ans += dp[S]
    ans %= MOD

print(ans)

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

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

for i in range(N):
    for j in range(S):
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        
        if j+A[i]<=S:
            if j==0:
                dp[i+1][j+A[i]] += dp[i][j]*(i+1)
            else:
                dp[i+1][j+A[i]] += dp[i][j]
            
            dp[i+1][j+A[i]] %= MOD

ans = 0

for i in range(1, N+1):
    ans += dp[i][S]*(N-i+1)
    ans %= MOD

print(ans)

Solution (Python):
n, s = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0] * (s + 1) for _ in range(n + 1)]
for i in range(n):
    dp[i][0] = 1
for i in range(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
ans = 0
for i in range(n + 1):
    ans += dp[i][s]
    ans %= mod
print(ans)

Solution (Python):
n,s=map(int,input().split())
a=[int(j)for j in input().split()]
mod=998244353
ans=0
import numpy as np
dp=np.zeros(3001,np.int64)
for i in a:
    dp[0]+=1
    dp[i:]+=dp[:-i].copy()
    dp%=mod
    ans+=dp[s]
    ans%=mod
print(ans)

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 998244353  

def solve(N: int, S: int, A: "List[int]"):
    dp = [[0] * 2 for _ in range(S + 1)]
    for i, v in enumerate(A):
        if v > S:
            continue
        for s in range(S + 1)[::-1]:
            if dp[s][0] > 0 and s + v <= S:
                dp[s + v][0] += dp[s][0]
                dp[s + v][1] += dp[s][0] * (N - i)
                dp[s + v][0] %= MOD
                dp[s + v][1] %= MOD
        dp[v][0] += i + 1
        dp[v][1] += (i + 1) * (N - i)
    print(dp[S][1] % 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))  
    S = int(next(tokens))  
    A = [int(next(tokens)) for _ in range(N)]  
    solve(N, S, A)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
def input():
    return sys.stdin.readline()[:-1]
n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp0 = [[0 for i in range(s+1)]for i in range(n+1)]
dp1 = [[0 for i in range(s+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(s+1):
        if j==0:
            b=1
        else:
            b=0
        dp0[i][j] += (dp0[i-1][j]+b)
        dp0[i][j] %= mod
        dp1[i][j] += (dp1[i-1][j]+dp0[i-1][j]+b)
        dp1[i][j] %= mod
        if j+a[i-1]<=s:
            dp0[i][j+a[i-1]] += (dp0[i-1][j]+b)
            dp0[i][j+a[i-1]] %= mod
            dp1[i][j+a[i-1]] += (b+dp0[i-1][j])
            dp1[i][j+a[i-1]] %= mod

        dp0[i][j]%=mod
        dp1[i][j]%=mod

print(dp1[n][s])

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

ptn = [0] * (s + 1)
ptn[0] = 1
ans = 0
for i in range(n):
    for j in range(s + 1)[::-1]:
        if j + a[i] > s:
            continue
        ptn[j + a[i]] += ptn[j]
    ans += ptn[s]
    ans %= MOD
    ptn[0] += 1

print(ans)

Solution (Python):
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    ans = 0
    dp = np.zeros(s+1,dtype=int)
    for j in range(n):
        dp[0] += 1
        aj = a[j]
        ndp = dp*1
        if s >= aj:
            dp[s-aj] *= (n-j)
        ndp[aj:] += dp[:-aj]
        ndp %= mod
        dp = ndp
    print(dp[s])
    return

if __name__ == '__main__':
    main()

Solution (Python):
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    ans = 0
    dp = np.zeros(s+1,dtype=int)
    for j in range(n):
        dp[0] += 1
        aj = a[j]
        ndp = dp*1
        if s >= aj:
            dp[s-aj] *= (n-j)
        ndp[aj:] += dp[:-aj]
        ndp %= mod
        dp = ndp
    ans = (ans+dp[s]*(n-j))%mod
    print(ans)
    return

if __name__ == '__main__':
    main()

Solution (Python):
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp00=[0]*(s+1)
dp01=[0]*(s+1)
dp10=[0]*(s+1)
dp11=[0]*(s+1)
dp20=[0]*(s+1)
dp21=[0]*(s+1)
dp00[0]=1
for i in range(n):
  for j in range(s+1):
    if i%2==0:
      if j>=a[i]:
        dp11[j]=(dp00[j-a[i]]+dp10[j-a[i]]+dp00[j]+dp10[j])%mod
        dp21[j]=(dp00[j-a[i]]+dp10[j-a[i]]+dp00[j]+dp10[j]+dp20[j])%mod
      else:
        dp01[j]=dp00[j]%mod
        dp11[j]=(dp00[j]+dp10[j])%mod
        dp21[j]=(dp00[j]+dp10[j]+dp20[j])%mod
    else:
      if j>=a[i]:
        dp10[j]=(dp01[j-a[i]]+dp11[j-a[i]]+dp01[j]+dp11[j])%mod
        dp20[j]=(dp01[j-a[i]]+dp11[j-a[i]]+dp01[j]+dp11[j]+dp21[j])%mod
      else:
        dp00[j]=dp01[j]%mod
        dp10[j]=(dp01[j]+dp11[j])%mod
        dp20[j]=(dp01[j]+dp11[j]+dp21[j])%mod
if n%2==1:
  print(dp21[s])
else:
  print(dp20[s])

Solution (Python):
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp0=[[0]*(s+1) for i in range(n+1)]
dp1=[[0]*(s+1) for i in range(n+1)]
dp2=[[0]*(s+1) for i in range(n+1)]
dp0[0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp1[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
    else:
      dp0[i+1][j]=dp0[i][j]%mod
      dp1[i+1][j]=(dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
print(dp2[n][s])

Solution (Python):
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp0=[[0 for i in range(s+1)] for j in range(n+1)]
dp1=[[0 for i in range(s+1)] for j in range(n+1)]
dp2=[[0 for i in range(s+1)] for j in range(n+1)]
dp0[0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp1[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
    else:
      dp0[i+1][j]=dp0[i][j]%mod
      dp1[i+1][j]=(dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
print(dp2[n][s])

Solution (Python):
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

dp=[0 for n in range(3001)]
c=0
for n in range(N):
    a=A[n]
    for s in range(0,S+1)[::-1]:
        if s+a<=S:
            dp[s+a]+=dp[s]
            dp[s+a]%=mod

    dp[a]+=n+1
    dp[a]%=mod
    c+=dp[S]
    c%=mod

print(c)

Solution (Python):


import numpy as np


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

MOD = 998244353


def add_elements(w, i):
    a = A[i]
    w[a:] += w[:-a].copy()
    if a <= S:
        w[a] += i + 1
    w %= MOD


def main():
    w = np.zeros(S + 1, dtype=int)
    ans = 0
    for i in range(N):
        add_elements(w, i)
        ans = (ans + w[S]) % MOD
    
    print(ans)


if __name__ == "__main__":
    main()

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

for i, a in enumerate(A):
    dp[0] +=1
    if a > S:
        continue

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

    for j, x in enumerate(dp[:S-a]):
        dp[j+a] += x
print(ans)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read


sys.setrecursionlimit(10**7)






def run():
    N, S = map(int, sysread().split())
    A = [0]+ list(map(int,sysread().split()))
    dp = [[0] * (S+1) for _ in range(N+1)]
    if A[1] <= S:
        dp[1][A[1]] = 1
    mod = 998244353
    for r in range(1, N):
        if A[r+1] <= S:
            dp[r+1][A[r+1]] += r+1
            dp[r + 1][A[r + 1]] %= mod
        for s in range(1,S+1):
            dp[r+1][s] += dp[r][s] + dp[r][s] - dp[r-1][s]
            dp[r+1][s] %= mod
            if s + A[r+1] <= S:
                dp[r+1][s+A[r+1]] += dp[r][s] - dp[r-1][s]
                dp[r + 1][s + A[r + 1]] %= mod
    print(dp[N][S] % mod)


if __name__ == "__main__":
    run()

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

Solution (Python):
import sys

input = sys.stdin.buffer.readline
n, s = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]

mod = 998244353


dp[0][0] = 1
ans = 0
for i in range(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
    dp[ni][0] += 1
    ans += dp[ni][s]
    ans %= mod
print(ans)

Solution (Python):
n, s = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]

mod = 998244353


dp[0][0] = 1
ans = 0
for i in range(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
    dp[ni][0] += 1
    ans += dp[ni][s]
    ans %= mod
print(ans)

Solution (Python):

import sys

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

N, S = lr()
A = lr()
MOD = 998244353
dp = [0] * (S+1)

answer = 0
for a in A:
    dp[0] += 1
    for x in range(S, a-1, -1):
        dp[x] += dp[x-a]
    answer += dp[-1]
    answer %= MOD

print(answer%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, s = map(int, input().split())
    dp = [0] * (s + 1)
    res = 0
    for a in map(int, input().split()):
        dp[0] += 1
        for i in range(s - a, -1, -1):
            dp[i + a] += dp[i]
            if dp[i + a] >= MOD:
                dp[i + a] -= MOD
        res += dp[s]
        if res >= MOD:
            res -= MOD

    print(res)
resolve()

Solution (Python):
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        dp[0] +=1
        if a > S:
            continue

        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()

Solution (Python):
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        dp[0] = i+1
        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()

Solution (Python):
def main():
    MOD = 998244353

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

    dp = [0] * (S + 1)
    ans = 0
    for x in A:
        dp[0] += 1
        for j in range(S, x - 1, -1):
            dp[j] = (dp[j] + dp[j - x]) % MOD
        ans = (ans + dp[S]) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, S = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        dp[i+1][0] += 1
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
            if j + A[i] <= S:
                dp[i+1][j+A[i]] += dp[i][j]
                dp[i+1][j+A[i]] %= MOD
    ans = sum(dp[i][S] for i in range(N+1)) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353


def main():
    N, S = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        dp[i+1][0] += 1
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
            if j + A[i] <= S:
                dp[i+1][j+A[i]] += dp[i][j]
                dp[i+1][j+A[i]] %= MOD
    ans = 0
    for i in range(N+1):
        ans += dp[i][S]
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 998244353


def main():
    N, S = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [[0]*(S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        dp[i+1][0] += 1
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= MOD
            if j + A[i] <= S:
                dp[i+1][j+A[i]] += dp[i][j]
                dp[i+1][j+A[i]] %= MOD
    ans = 0
    for i in range(N+1):
        ans += dp[i][S]
    print(ans % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
U = 3001

ans = 0
dp = np.zeros(U, dtype=np.int64)
dp[0] = 1

for a in A:
    newDP = np.copy(dp)
    newDP[a:] += dp[:-a]
    newDP[0] += 1
    newDP %= mod
    dp = newDP

    ans += dp[S]
    ans %= mod

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 a in A:
    dp[0] += 1
    for s in range(S + 1)[::-1]:
        if s + a <= S:
            dp[s + a] = (dp[s + a] + dp[s]) % MOD
    ans += dp[S]
    ans %= MOD

print(ans)

Solution (Python):
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 l in range(N):
  r = N - l
  x = a[l]
  if x > S: continue
  for i in range(S, 0, -1):
    if i + x > S: continue
    if i + x == S:
      dp[S] += dp[i] * r
      dp[S] %= mod
    else:
      dp[i + x] += dp[i]
      dp[i + x] %= mod
  if x == S:
    dp[S] += (l + 1) * r
    dp[S] %= mod
  else:
    dp[x] += l + 1
    dp[x] %= mod
  
print(dp[-1])

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): 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 LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,S = MI()
A = LI()
dp = FILL2(0,N+1,S+1)
for i in range(N):
    for j in range(S+1):
        if j>0 and j+A[i]<=S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] %= MOD
        elif j==0 and A[i]<=S:
            dp[i+1][A[i]] += i+1
            dp[i+1][A[i]] %= MOD
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
ans = 0
for i in range(N+1):
    ans += dp[i][S]
    ans %= MOD
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
def input(): return sys.stdin.readline().rstrip()

def main():
    N,S=map(int,input().split())
    A=list(map(int,input().split()))
    dp0=[[0 if i!=0 else 1 for i in range(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)]
    for i in range(N):
        for j in range(S+1):
            b=int(j==0)
            dp1[i+1][j]+=dp1[i][j]+b
            dp2[i+1][j]+=dp1[i][j]+dp2[i][j]+b
            dp1[i+1][j]%=MOD
            dp2[i+1][j]%=MOD
            if j+A[i]<=S:
                dp1[i+1][j+A[i]]+=dp1[i][j]+b
                dp2[i+1][j+A[i]]+=dp1[i][j]+b
                dp1[i+1][j+A[i]]%=MOD
                dp2[i+1][j+A[i]]%=MOD
    print(dp2[-1][-1])

if __name__ == '__main__':
    main()

Solution (Python):

import sys
input = sys.stdin.buffer.readline


def read_int_n():
    return list(map(int, input().split()))


def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()

Solution (Python):


def main():
    MOD = 998244353

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

    ans = 0
    dp = [0] * (S + 1)
    for i, a in enumerate(A, start=1):
        dp[0] = i  
        ans += dp[S]  
        if S >= a:
            ans += dp[S - a]  
        ans %= MOD
        for s in reversed(range(a, S + 1)):
            dp[s] += dp[s - a]
            dp[s] %= MOD

    print(ans)


if __name__ == '__main__':
    main()

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

Solution (Python):
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random



def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def my_main():
        n, s = inp()
        da = inp()
        dp = [[0 for i in range(s+1)] for i in range(n+1)]
        sm = [0 for i in range(s+1)]
        dp[0][0] = sm[0] = 1
        mod = 998244353
        for i in range(1, n+1):
            now = da[i-1]
            dp[i][0] = 1
            for j in range(s+1):
                if j>=now:
                    dp[i][j] += sm[j-now]
                dp[i][j] %= mod
            for j in range(s+1):
                sm[j] += dp[i][j]
                sm[j] %= mod
        ans = 0
        for i in range(n+1):
            ans += dp[i][s]*(n-i+1)
            ans %= mod
        print ans



my_main()

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N,S=MI()
    A=LI()
    
    dp=[[0]*(S+1)for _ in range(N+1)]
    
    
    
    for i in range(N):
        a=A[i]
        dp[i][0]+=1
        for j in range(S+1):
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
            if j+a<=S:
                dp[i+1][j+a]=(dp[i+1][j+a]+dp[i][j])%mod
                
    ans=0
    for i in range(N+1):
        ans=(ans+dp[i][-1])%mod
        
    print(ans)
                
            
    
            
        

main()

Solution (Python):
import numpy as np
MOD = 998244353
def main():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [np.zeros(s+1, dtype=np.int64) for i in range(n+1)]
    ans = 0
    for i in range(n):
        if a[i] <= s:
            dp[i+1][a[i]:] = dp[i][:-a[i]]
            dp[i+1][a[i]] += i+1
        dp[i+1][:s] += dp[i][:s]
        dp[i+1][dp[i+1] >= MOD] -= MOD
        ans += dp[i+1][s] * (n-i)
        ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

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

mod = 998244353

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

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]
        dp0[i+1][j] %= mod

        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp1[i+1][j] %= mod

        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        dp2[i+1][j] %= mod

        if j+A[i] <= S:
            dp1[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp1[i+1][j+A[i]] %= mod
        
            dp2[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+A[i]] %= mod

print(dp2[N][S])

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













dp0 = [[0] * (s + 1) for _ in range(n + 1)]
dp1 = [[0] * (s + 1) for _ in range(n + 1)]
dp0[0][0] = 1
ans = 0
for i in range(n):
    for j in range(s + 1):
        
        dp0[i + 1][j] += dp0[i][j]
        dp0[i + 1][j] %= MOD
        dp1[i + 1][j] += dp0[i][j] + dp1[i][j]
        dp1[i + 1][j] %= MOD

        if j + a[i] <= s:
            dp1[i + 1][j + a[i]] += dp0[i][j] + dp1[i][j]
            dp1[i + 1][j + a[i]] %= MOD

    ans += dp1[i + 1][s]
    ans %= MOD






print(ans)