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
import copy
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 998244353  


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, S: int, A: "List[int]"):
    dp = array(S+1, 3, initial=0)
    dp_past = array(S+1, 3, initial=0)
    dp[0][0] = 1
    for i in range(N):
        dp_past, dp = dp, dp_past
        
        for s in range(S+1):
            dp[s][:] = dp_past[s]
            
            if s == A[i]:
                dp[s][1] += i+1
                dp[s][1] %= MOD
            if s-A[i] >= 0:
                dp[s][0] += dp_past[s-A[i]][0]
                dp[s][0] %= MOD
                dp[s][1] += dp_past[s-A[i]][1]
                dp[s][1] %= MOD
                dp[s][2] += (dp[s][1]-dp_past[s][1]) * (N-i)
                dp[s][2] %= MOD

    print(dp[S][2])

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


n, s = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [[None] * (s+1) for _ in range(n+1)]
M = 998244353


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

for i in range(1,n+1):
    for j in range(1, s+1):
        dp[i][j] = dp[i-1][j]
        if j-a[i-1]>=0:
            dp[i][j] += dp[i-1][j-a[i-1]]
        dp[i][j] %= M
print(sum((dp[i][s] for i in range(n+1)))%M)

Solution (Python):
import sys
from copy import copy
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  
mod = 998244353

n, s = map(int, input().split())
a = [0]
a += list(map(int, input().split()))

dp = [[0]*(3010) for i in range(n+2)]

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

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

dp=[0]*(s+1)
for i in range(n+1):
    dp[0]=1
ans=0

for i,w in enumerate(a):
    for j in range(s-w,-1,-1):
        dp[j+w]+=dp[j]
        dp[j+w]%=998244353
    ans+=dp[-1]
    ans%=998244353
    dp[0]+=1

print(ans)

Solution (Python):
import numpy as np

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

dp=[np.zeros(s+1,dtype=np.int64) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
ans=0

for i,w in enumerate(a):
    dp[i]+=dp[i-1]
    dp[i][w:]+=dp[i-1][:-w]
    dp[i]%=998244353
    ans+=dp[i][-1]
    ans%=998244353

print(ans)

Solution (Python):
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*6003
for a in a:
 for j in range(s,0,-1):d[a+j]+=d[j]
 i+=1;d[a]+=i;c+=d[s]
print(c%998244353)

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

Solution (Python):
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*6003
for a in a:
 for j in range(s,0,-1):d[a+j]+=d[j]
 i+=1;d[a]+=i;c+=d[s]
print(c%(998244353))

Solution (Python):
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*6003
for a in a:
 for j in range(s,0,-1):d[a+j]+=d[j]
 i+=1;d[a]+=i;c+=d[s]
print(c%(998244353))

Solution (Python):
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*6003
for a in a:
 for j in range(s,0,-1):d[a+j]+=d[j]
 d[a]-=~i;c+=d[s];i+=1
print(c%(998244353))

Solution (Python):
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*6003
for a in a:
 for j in range(s,0,-1):d[a+j]+=d[j]
 d[a]-=~i;c+=d[s];i+=1
print(c%(998244353))

Solution (Python):
n,s,*a=map(int,open(0).read().split())
d=[0]*3001
c=0
for i,a in enumerate(a):
    for j in range(s-a,0,-1):d[a+j]+=d[j]
    d[a]-=~i
    c+=d[s]
print(c%(998244353))

Solution (Python):
n,s,*a=map(int,open(0).read().split())
d=[0]*3001
c=0
for i,a in enumerate(a):
    for j in range(s-a,0,-1):d[a+j]+=d[j]
    d[a]-=~i
    c+=d[s]
print(c%(998244353))

Solution (Python):
import sys
input = sys.stdin.readline
'''
n, m = map(int, input().split())
n = int(input())
A = list(map(int, input().split()))
S = input().strip()
for test in range(int(input())):
'''
inf = 100000000000000000  
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(s, A[i] - 1, -1):
        dp[j] += dp[j - A[i]]
        dp[j] %= mod
    ans += dp[s]
    ans %= mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 998244353
    
    dp = np.zeros(3000+10,dtype=int)
    ans = 0
    
    for num in a:
        dp[0] += 1
        dp[num:] += dp[:-num].copy()
        dp %= MOD
        ans += dp[S]
        
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
mod = 998244353
N, S = list(map(int, input().split()))
A = list(map(int, input().split()))

ans = 0
num = [0] * 6020
for i in range(N):
    for j in range(3010, 0, -1):
        num[A[i]+j] += num[j]
        num[A[i]+j] %= mod
    num[A[i]] += i+1
    num[A[i]] %= mod
    ans += num[S] * (N - i)
    ans %= mod
    num[S] = 0
print(ans)

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)]
dp[0][0] = 1

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

print(dp[n][s] % MOD)

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 in range(N):
        dp[0] += 1
        dp2 = [0] * (S + 1)
        for j in range(S+1):
            dp2[j] += dp[j]
            if j + A[i] <= S:
                dp2[j + A[i]] += dp[j] 
                dp2[j + A[i]] %= MOD

        dp = dp2

        ans += dp[S]
        ans %= MOD

    
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)

mod = 998244353


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

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

    for a in A:
        for s in range(S, -1, -1):
            d1 = dp[s][0]
            d2 = (dp[s][1] + (0 if s - a < 0 else dp[s - a][1]) + d1) % mod
            d3 = (dp[s][2] + (0 if s - a < 0 else dp[s - a][1]) + d2) % mod
            dp[s] = (d1, d2, d3)

    print((dp[S][2] - dp[S][1]) % mod)


if __name__ == "__main__":
    main()

Solution (Python):
N,S=map(int,input().split())
A= list(map(int,input().split()))
mod=998244353
c=0
M=[[0 for t in range(S+1)] for j in range(N)]
M[0][0]=2
if A[0]<=S:
 M[0][A[0]]=1
if A[0]==S:
 c+=1
for i in range(1,N):
 M[i][0]+=(i+2)
 for k in range(1,S+1):
  M[i][k]+=M[i-1][k]
  M[i][k]%=mod
  if k>=A[i] :
   M[i][k]+=M[i-1][k-A[i]]
   M[i][k]%=mod
 c+=M[i][S]
 c%=mod
print(c)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, s = LI()
A = LI()
dp = [[0] * (s + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(1, s + 1):
        if j == A[i]:
            dp[i + 1][j] += i + 1
        elif j > A[i]:
            dp[i + 1][j] += dp[i][j - A[i]]
        if j == s:
            dp[i + 1][j] = dp[i + 1][j] * (n - i) % mod
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod


print(dp[n][s])

Solution (Python):

MOD = 998244353


def main():
    global MOD
    N,S = map(int, input().split())
    A = list(map(int, input().split()))
    dp0 = [[0 for i in range(S+1)] for j in range(N)]
    dp1 = [[0 for i in range(S+1)] for j in range(N)]
    dp2 = [[0 for i in range(S+1)] for j in range(N)]


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

    print(dp2[N-1][S]%MOD)

main()

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

    N, S = map(int, input().split())
    A = tuple(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):
        DP0[i + 1][0] = DP0[i][0] 
        DP1[i + 1][0] = DP0[i][0] + DP1[i][0]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP1[i + 1][j] = DP1[i][j] 
        else:
            for j in range(1, a):
                DP1[i + 1][j] = DP1[i][j] 
            for j in range(a, S + 1):
                DP1[i + 1][j] = (DP1[i][j] + DP0[i][j - a] + DP1[i][j - a]) % MOD
                

        DP2[i + 1][S] = (DP1[i][S] + DP2[i][S])
        if a <= S:
            DP2[i + 1][S] += DP0[i][S - a] + DP1[i][S - a]
        DP2[i + 1][S] %= MOD

    print (DP2[N][S])

    
    

if __name__ == '__main__':
    main()

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

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

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

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

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

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

Solution (Python):

import copy

r = 998244353

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

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


itbl = {}
rtbl = {}

for i in range(n):
    ai = a[i]
    
    if ai <= s:
        nitbl = copy.copy(itbl)        
        if ai in nitbl:
            nitbl[ai] = (nitbl[ai] + i + 1) % r
        else:
            nitbl[ai] = i + 1

        if ai in rtbl:
            rtbl[ai] += (i + 1) * (n - i)
        else:
            rtbl[ai] = (i + 1) * (n - i)

        for sk in itbl:
            if sk + ai <= s:
                if sk + ai in nitbl:
                    nitbl[sk + ai] = (nitbl[sk + ai] + itbl[sk]) % r
                else:
                    nitbl[sk + ai] = itbl[sk]
                    
                if sk + ai in rtbl:
                    rtbl[sk + ai] = (rtbl[sk + ai] + itbl[sk] * (n - i)) % r
                else:
                    rtbl[sk + ai] = (itbl[sk] * (n - i)) % r
            
        itbl = nitbl
    
print(rtbl.get(s, 0))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    a = LI()
    r = 0
    dp = [0] * (s+1)
    dp[0] = 1
    for i in range(n):
        ai = a[i]
        if ai > s:
            dp[0] += 1
            continue
        dp[s] += dp[s-ai] * (n-i)
        dp[s] %= mod2
        for j in range(s-1, ai-1, -1):
            dp[j] += dp[j-ai]
            dp[j] %= mod2
        dp[0] += 1

    return dp[-1] % mod2


print(main())

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)]
dp[0][0] = 1

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

ans = 0

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

print(ans)

Solution (Python):

import numpy as np
mod = 998244353
N, S = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

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

for k in range(0, N):
  dp[k+1,:] += (2 * dp[k,:] - dp[k-1,:]) % mod
  if S > A[k+1]:
    dp[k+1, A[k+1]+1:] += (dp[k, 1:S-A[k+1]+1] - dp[k-1, 1:S-A[k+1]+1]) % mod
  if A[k+1] <= S:
    dp[k+1,A[k+1]] += k+1

print(dp[N,S] % mod)

Solution (Python):
MOD = 998244353
n, S = map(int, input().split())
a = list(map(int, input().split()))
dp1 = [[0 for _ in range(S+1)] for _ in range(n+1)]
dp2 = [[0 for _ in range(S+1)] for _ in range(n+1)]
for i in range(1, n+1): 
	for s in range(S+1):
		if s < a[i-1]:
			dp1[i][s] = dp1[i-1][s] % MOD
		elif s == a[i-1]:
			dp1[i][s] = (dp1[i-1][s] + i) % MOD
		else:
			dp1[i][s] = (dp1[i-1][s] + dp1[i-1][max(s-a[i-1],0)]) % MOD

for i in range(1, n+1): 
	for s in range(S+1):
		if s < a[i-1]:
			dp2[i][s] = dp2[i-1][s] % MOD
		elif s == a[i-1]:
			dp2[i][s] = (dp2[i-1][s] + i*(n-i+1)) % MOD
		else:
			dp2[i][s] = (dp2[i-1][s] + dp1[i-1][max(s-a[i-1],0)] * (n-i+1)) % MOD

print(dp2[n][s])

Solution (Python):
from numpy import *
M=998244353
N,S,*A=map(int,open(0).read().split())
a=0
f=zeros(S+1,int)
for b in A:
  f[0]+=1
  f[b:] += f[:-b].copy()
  f%=M
  a+=f[S]
print(a%M)

Solution (Python):
mod = 998244353



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

DP = [0]*S
DP[0] = 1
ans = 0

for i in range(N):
    
    
    a = A[i]
    for j in range(S):
        k = S-1-j
        if k+a <S:
            if k==0:
                DP[k+a] += i+1
            else:
                DP[k+a] += DP[k]
        elif k+a ==S:
            if k==0:
                ans += (i+1)*(N-i)
                ans %= mod
            else:
                ans += DP[k]*(N-i)
                ans %= mod


print(ans)

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

dp = [[1] + [0] * s for _ in range(n + 1)]
ans = 0
for i in range(n):
    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 += dp[i + 1][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) for _ in range(n + 1)]
ans = 0
for i in range(n):
    dp[i][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 += dp[i + 1][s]
    ans %= MOD

print(ans)

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

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

            if j+a > S: continue
            dp1n[j+a] = (dp1n[j+a] + dp1i[j] + (dp0i[j] * (i+1))) % MOD
            dp2n[j+a] = (dp2n[j+a] + (dp1i[j] * (N-i)) + (dp0i[j] * (i+1) * (N-i))) % MOD

    print(dp2[N][S])

if __name__ == '__main__':
    main()

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

    ans = Mint()
    q = [Mint() for _ in range(S+1)]
    for a in A:
        q[0] += 1
        for i in range(S-a,-1,-1): q[i+a] += q[i]
        ans += q[S]
    print(ans)

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

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

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

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



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

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

print(ans)

Solution (Python):


def main():
    MOD = 998244353

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

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        if x > S: continue
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
 

m = np.zeros((S+1,3))
p = np.zeros((S+1,3))
p[0,0] = 1


for i in range(1,N+1):
    
    
    m[:,0] = p[:,0]
    m[:,1] = p[:,0] + p[:,1]  
    m[:,2] = p[:,0] + p[:,1] + p[:,2]  

    
    m[x[i-1]:,1] += p[:-x[i-1],0] + p[:-x[i-1],1]
    m[x[i-1]:,2] += p[:-x[i-1],0] + p[:-x[i-1],1]

    p[:,0] = m[:,0] % 998244353
    p[:,1] = m[:,1] % 998244353
    p[:,2] = m[:,2] % 998244353
            
print(int(p[S,2]))

Solution (Python):
import numpy as np
n,s = map(int, input().split( ))

a = np.array(list(map(int, input().split( ))))

dp = np.array([[0]*3001 for i in range(n)])
dp[0][0] = 1
dp[0][a[0]] = 1

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

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


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

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

print(ans)

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

mod = 998244353

sum_array = [0] * S
ans = 0

for i, A in enumerate(A_array):
    if A > S:
        continue
    if A == S:
        ans = (ans + (i+1) * (N-i)) % mod
        continue
    ans = (ans + sum_array[S-A] * (N-i)) % mod
    for j in range(S-1, A, -1):
        sum_array[j] = (sum_array[j] + sum_array[j-A]) % mod
    sum_array[A] = (sum_array[A] + (i+1)) % mod
    
print(ans)

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

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

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

print(ans)

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

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

ans = 0
dp = [[0]*(S+1) for _ in range(N+1)]
for i in range(N):
    dp[i][0] += 1       
    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 += dp[i+1][S]    
    ans %= MOD

print(ans)

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

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

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

print(ans)

Solution (Python):

import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

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

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

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


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

dp[0][0] = 1
sumdp[0] = 1

for i in range(1,N+1):
    a = A[i-1]
    if a <= S:
        dp[i][a] += i
    for j in range(1,S+1):
        if j+a > S:
            break
        dp[i][j+a] += sumdp[j]
        dp[i][j+a] %= MOD
    for j in range(S+1):
        sumdp[j] = (sumdp[j] + dp[i][j]) % MOD
    
ans = 0
for i in range(1,N+1):
    ans = (ans + dp[i][S] * (N+1-i)) % MOD
print(ans % MOD)

Solution (Python):
import numpy as np

def main():
    n, s = map(int, input().split())
    nums = [int(c) for c in input().split()]
    mod = 998244353
    dp = np.zeros(s+1, dtype=np.int)
    ans = 0

    for i, num in enumerate(nums, 1):
        dp[0] = i
        if num <= s:
            dp[num:] = dp[num:] + dp[:-num]
            
        dp %= mod
        ans = (ans + dp[-1]) % mod
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

fwd_acc = np.zeros((n + 1, s + 1), dtype=np.int64)
fwd_acc[0][0] = 1

ans = 0
MOD = 998244353
for i, a in enumerate(aaa, start=1):
    fwd_acc[i] = fwd_acc[i - 1]
    fwd_acc[i][0] = i
    if a <= s:
        fwd_acc[i][a:] = fwd_acc[i][a:] + fwd_acc[i][:-a]
    fwd_acc[i] %= MOD
    ans = (ans + fwd_acc[i][s]) % MOD
    
    
print(ans)

Solution (Python):
M = 998244353
N, S = map(int, input().split())

ans = 0
prev = [0]*S
for i, a in enumerate(map(int, input().split()), 1):
  if a > S:
    continue
  prev[0] = i
  ans += prev[S-a]*(N-i+1)
  for j, s in enumerate(prev[:S-a], a):
    prev[j] += s
print(ans%M)

Solution (Python):
M = 998244353
N, S = map(int, input().split())

ans = 0
prev = [0]*S
for i, a in enumerate(map(int, input().split()), 1):
  if a > S:
    continue
  prev[0] = i
  ans += prev[S-a]*(N-i+1)%M
  for j, s in enumerate(prev[:S-a], a):
    if s:
      prev[j] += s
print(ans%M)

Solution (Python):
M = 998244353
N, S = map(int, input().split())

ans = 0
prev = [0]*S
for i, a in enumerate(map(int, input().split()), 1):
  if a > S:
    continue
  prev[0] = i
  ans += prev[S-a]*(N-i+1)
  for j, s in enumerate(prev[:S-a], a):
    prev[j] += s
print(ans%M)

Solution (Python):
M = 998244353
N, S = map(int, input().split())

ans = 0
prev = [0]*S
for i, a in enumerate(map(int, input().split()), 1):
  if a > S:
    continue
  prev[0] = i
  ans += prev[S-a]*(N-i+1)
  for j, s in enumerate(prev[:S-a], a):
    prev[j] += s
print(ans%M)

Solution (Python):
M = 998244353
N, S = map(int, input().split())

ans = 0
prev = [0]*S
for i, a in enumerate(map(int, input().split()), 1):
  if a > S:
    continue
  prev[0] = i
  ans = (ans + prev[S-a]*(N-i+1)) % M
  for j, s in enumerate(prev[:S-a], a):
    prev[j] += s
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,a in enumerate(A):
    dp[i+1][0] = 1
    if a <= S: dp[i+1][a] = 1
    for j in range(S+1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
    for j in range(S+1):
        if j+a > S: break
        dp[i+1][j+a] += dp[i][j]
        dp[i+1][j+a] %= MOD
print(sum(row[-1] for row in dp)%MOD)

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

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

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