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())
dp=[0]*3001
res=0
for i,a in enumerate(map(int,input().split())):
    for w in range(S-a,0,-1):
        dp[w+a]+=dp[w]
    dp[a]+=i+1
    res+=dp[S]
print(res%998244353)

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

    dp = [0] * (s + 1)

    for i, x in enumerate(a):
        if x >= s:
            if x == s:
                dp[s] += (i + 1) * (n - i)
                dp[s] %= mod
            continue

        dp[s] += dp[s-x] * (n - i)
        dp[s] %= mod

        for j in range(s-x-1, 0, -1):
            dp[j+x] += dp[j]
            dp[j+x] %= mod

        dp[x] += i + 1
        dp[x] %= mod

    print(dp[s])

main()

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

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

        if j>=a[i]:
            dp[i+1][j]+=dp[i][j-a[i]]
        
        dp[i+1][j]%=mod
    ans+=dp[i+1][S]
    ans%=mod


print(ans)

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

Solution (Python):
import sys

def main():
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

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

if __name__ == '__main__':
    main()

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

DP = [0 for s in range(S+1)]
ans = 0
for i in range(N):
  a = A[i]
  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
readline = sys.stdin.readline

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))








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

for i in range(N):
  for k in range(S + 1):
    
    dp[i + 1][0][k] += dp[i][0][k]
    dp[i + 1][0][k] %= DIV

    
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][0][k]
      dp[i + 1][1][k + A[i]] += dp[i][1][k]
      dp[i + 1][1][k + A[i]] %= DIV

    
    dp[i + 1][1][k] += dp[i][0][k]
    dp[i + 1][1][k] += dp[i][1][k]
    dp[i + 1][1][k] %= DIV

    
    dp[i + 1][2][k] += dp[i][2][k]
    dp[i + 1][2][k] += dp[i][1][k]
    dp[i + 1][2][k] %= DIV

print((dp[-1][1][-1] + dp[-1][2][-1]) % DIV)

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

DIV = 998244353
N,S = map(int,readline().split())
A = list(map(int,readline().split()))








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

for i in range(N):
  for k in range(S + 1):
    
    dp[i + 1][0][k] += dp[i][0][k]
    dp[i + 1][0][k] %= DIV

    
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][0][k]
      dp[i + 1][1][k + A[i]] %= DIV

    
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][1][k]
      dp[i + 1][1][k + A[i]] %= DIV
      
    
    dp[i + 1][1][k] += dp[i][0][k]
    dp[i + 1][1][k] %= DIV
    
    
    dp[i + 1][1][k] += dp[i][1][k]
    dp[i + 1][1][k] %= DIV

    
    dp[i + 1][2][k] += dp[i][1][k]
    dp[i + 1][2][k] %= DIV
    
    
    dp[i + 1][2][k] += dp[i][2][k]
    dp[i + 1][2][k] %= DIV

print((dp[-1][1][-1] + dp[-1][2][-1]) % DIV)

Solution (Python):
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353


dp=[0 for i in range(s+1)]
ans=0
for i in range(n):
    now=A[i]
    for q in range(s-now,-1,-1):
        dp[q+now]+=dp[q]%mod
    if A[i]<=s:
        dp[A[i]]+=i+1
    ans+=dp[s] 
    ans=ans%mod
    
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)]
dp[0][0] = 1
if A[0] <= S:
    dp[0][A[0]] = 1
for i in range(1,N):
    for j in range(S+1):
        if j+A[i] <= S:
            dp[i][j+A[i]] += dp[i-1][j]
            dp[i][j+A[i]] %= mod
        dp[i][j] += dp[i-1][j]
        dp[i][j] %= mod
    dp[i][0] += 1
    dp[i][0] %= mod
    if A[i] <= S:
        dp[i][A[i]] += 1
        dp[i][A[i]] %= mod
ans = 0
for i in range(N):
    ans += dp[i][S]
ans %= mod
print(ans)

Solution (Python):
from collections import defaultdict

MOD = 998244353


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

    dp = [0] * S
    ans = 0
    for right in range(N):
        num = A[right]
        if num > S:
            continue
        elif num == S:
            ans = (ans + (right+1) * (N-right)) % MOD
            continue
        
        
        
        
        
        
        
        ans = (ans + dp[S-num] * (N-right)) % MOD
        for i in range(S-num-1, -1, -1):
            dp[i+num] += dp[i]
        dp[num] += right + 1
    print(ans)


if __name__ == "__main__":
    main()

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

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

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size,init_val=1):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = init_val


    def multiple(self,polynomial,MOD): 
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] 
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        self.f %= MOD
    
    def add(self,polynomial,MOD): 
        for dim,const in polynomial:
            self.f[dim] += const
            self.f %= MOD

    def get_coefficient(self,dim):
        return self.f[dim]



INF=10**20
def main():
    N,S=mi()
    A=list(mi())
    MOD=998244353

    F = PolySolver(3010,init_val=0)
    ans = 0
    for i in range(N):
        f = Polynomial(dim=A[i]) + Polynomial(const=1)
        F.add(Polynomial(const=1).values,MOD)
        F.multiple(f,MOD)
        ans += F.get_coefficient(S)
    
    print(ans % MOD)
    


if __name__ == "__main__":
    main()

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

class Polynomial:
    def __init__(self,dim=0,const=1):
        self.values = [(dim,const)]
    def __add__(self,other):
        return self.values + other.values


class PolySolver:
    def __init__(self,size,init_val=1):
        self.size = size
        self.f = np.zeros(size, np.int64)
        self.f[0] = init_val


    def multiple(self,polynomial,MOD): 
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] 
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        self.f %= MOD
    
    def add(self,polynomial,MOD): 
        for dim,const in polynomial:
            self.f[dim] += const
            self.f %= MOD

    def get_coefficient(self,dim):
        return self.f[dim]



INF=10**20
def main():
    N,S=mi()
    A=list(mi())
    MOD=998244353

    F = PolySolver(3010,init_val=0)
    ans = 0
    for i in range(N):
        f = Polynomial(dim=A[i]) + Polynomial(const=1)
        F.add(Polynomial(const=1).values,MOD)
        F.multiple(f,MOD)
        ans += F.get_coefficient(S)
    
    print(ans % MOD)
    


if __name__ == "__main__":
    main()

Solution (Python):
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def solve(N, S, A):
    mod = 998244353
    dp = np.zeros((N+1, S+1), dtype=np.int64)
    dp[0, 0] = 1
    ans = 0
    for i, a in enumerate(A, 1):
        for j in range(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
        dp[i, 0] += 1
        ans += dp[i, S]
    print(ans % mod)

numba_compile([
    [solve, "void(i8,i8,i8[:])"]
])

N, S = map(int, input().split())
A = np.array(input().split(), dtype=np.int64)
solve(N, S, A)

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]





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

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

mod=998244353

ans=0
dp=[0]*(S+1)
for a in A:
    dp[0]+=1
    for i in range(S,a-1,-1):
        dp[i]+=dp[i-a]
        dp[i]%=mod
    ans+=dp[-1]
    ans%=mod
    

print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]





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



mod=998244353

ans=0
dp=[0]*(S+1)
for a in map(int, input().split()):
    dp[0]+=1
    for i in range(S,a-1,-1):
        dp[i]+=dp[i-a]
        dp[i]%=mod
    ans+=dp[-1]
    ans%=mod
    

print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]





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



mod=998244353

ans=0
dp=[0]*(S+1)
for a in map(int, input().split()):
    dp[0]+=1
    for i in range(S,a-1,-1):
        dp[i]+=dp[i-a]
        dp[i]%=mod
    ans+=dp[-1]
    ans%=mod
    

print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]





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

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

mod=998244353

ans=0
dp=[0]*(S+1)
for a in A:
    dp[0]+=1
    for i in range(S,a-1,-1):
        dp[i]+=dp[i-a]
        dp[i]%=mod
    ans+=dp[-1]
    ans%=mod
    

print(ans)

Solution (Python):
import sys

def input(): return sys.stdin.readline()[:-1]





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

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

mod=998244353

ans=0
dp=[0]*(S+1)
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[-1]
    ans%=mod
    

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right

from collections import deque 



from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds





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

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

mod=998244353

ans=0
dp=[0]*(S+1)
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[-1]
    ans%=mod
    

print(ans)

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

def update(newval, length_elems):
  
  if newval<= s:
    new_state[newval][0] = length_elems
    new_state[newval][1] = length_elems
  
  for j in range(1, s+1):
    new_state[j][0] = (new_state[j][0] + old_state[j][0])%modval
    new_state[j][1] = (new_state[j][1] + old_state[j][0] + old_state[j][1])%modval
    if newval+j <= s:
      new_state[newval+j][0] = (new_state[newval+j][0] + old_state[j][0])%modval
      new_state[newval+j][1] = (new_state[newval+j][1] + old_state[j][0])%modval


old_state = [[0, 0] for _ in range(s+1)]
for i, newval in enumerate(a, 1):
  
  new_state = [[0, 0] for _ in range(s+1)]
  
  update(newval, i)
  
  old_state = new_state
print(new_state[s][1]%modval)

Solution (Python):

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


if __name__ == "__main__":
    resolve()

Solution (Python):
n,s=map(int,input().split())
now=[0]*(s+1)
mod1,mod2=10**9+7,998244353
mod=mod2

ans=0
for a in map(int,input().split()) :
    
    now[0]+=1
    for i in range(s,-1,-1):
        now[i]=(now[i]+(0 if i<a else now[i-a]))%mod
    ans=(ans+now[-1])%mod

print(ans)

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((n+1, s+1), dtype=np.int64)
    for i, v in enumerate(a):
        dp[i][0] += 1
        dp[i+1] += dp[i]
        if v <= s:
            dp[i+1][v:] += dp[i][:-v]
        dp[i+1] %= MOD
    ans = 0
    for i in range(n+1):
        ans += dp[i][s]
        ans %= MOD
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    MOD = 998244353
    N, S = list(map(int, input().split()))
    A = list(map(int, input().split()))
    dp = [[0] * (S + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for n in range(1, N + 1):
        a = A[n - 1]
        dp[n][0] = dp[n - 1][0] + 1
        for s in range(1, S):
            
            
            v = dp[n - 1][s]
            if s - a >= 0:
                v += dp[n - 1][s - a]
            dp[n][s] = v % MOD
        if S - a >= 0:
            
            dp[n][S] = dp[n - 1][S - a] * (N - n + 1) % MOD
    print(sum(dp[n][S] for n in range(N + 1)) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18

R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,s = inm()
a = inl()
dp = [[0]*(s+1) for i in range(n+1)]
for i in range(n):
    for j in range(1,s):
        dp[i+1][j] = dp[i][j]
    for j in range(1,s-a[i]+1):
        if dp[i][j]>0:
            dp[i+1][j+a[i]] = (dp[i+1][j+a[i]]+dp[i][j])%R
    if a[i]<=s:
        dp[i+1][a[i]] = (dp[i+1][a[i]]+i+1)%R
if False and DBG:
    for i in range(n+1):
        ddprint(dp[i])
sm = 0
for i in range(1,n+1):
    sm = (sm+dp[i][s]*(n+1-i))%R
print(sm)

Solution (Python):

import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353
N, S = map(int, readline().split())
A = list(map(int,readline().split()))
U = 3010
f = np.zeros(U,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):
n,s = map(int,input().split())
mod = 998244353
A = list(map(int,input().split()))
dp = [0 for _ in range(s+1)]
p = 0
F = {0}
for i in range(n):
    dp[0] += 1
    x = [[j,dp[j]] for j in F]
    for j in x:
        if j[0] + A[i] <= s:
            dp[j[0] + A[i]] += j[1]
            dp[j[0] + A[i]] %= mod
            F.add(j[0] + A[i])
    p += dp[s]
    p %= mod
print(p)

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

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

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

Solution (Python):

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

b = [[0]*(S+1) for _ in range(N+1)]
b[0][0] = int(S==0)
MOD = 998244353

for r in range(N):
    for s in range(S+1):
        b[r+1][s] += b[r][s]
        if s-A[r]>=0:
            b[r+1][s] += b[r][s-A[r]]
        if s==A[r] or s==0:
            b[r+1][s] += 1
        b[r+1][s] %= MOD

ans = 0
for i in range(N):  
    ans += b[i+1][S]
    ans %= MOD
    
print(ans)

Solution (Python):
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    import numpy as np
    dp = np.zeros(s+1, dtype=int)
    mod = 998244353
    ans = 0
    for i in range(n):
        dp[0] += 1
        dp[a[i]:] += dp[:-a[i]]
        dp%= mod
        ans += dp[-1]
        ans %= mod
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 998244353
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, s = map(int, readline().split())
    a = list(map(int, readline().split()))
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1

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

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
mod = 998244353
N, S = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
coef = np.zeros(3001, dtype=int)
ans = 0
for a in A:
    coef[0] += 1
    coef[a:] += coef[:-a]
    coef %= mod
    ans += coef[S]
    ans %= mod
print(ans)

Solution (Python):

MOD = 998244353
def resolve():
    
    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

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


if __name__ == "__main__":
    resolve()

Solution (Python):

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

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


if __name__ == "__main__":
    resolve()

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

    print(dp[S][2])

if __name__ == '__main__':
    main()

Solution (Python):
N, S = map(int, input().split())
mod = 998244353
A = list(map(int, input().split()))
L = [0 for _ in range(S+1)]
p = 0
F = {0}
for i in range(N):
    L[0] += 1
    X = [[j, L[j]] for j in F]
    for j in X:
        if j[0] + A[i] <= S:
            L[j[0]+A[i]] += j[1]
            L[j[0]+A[i]] %= mod
            F.add(j[0]+A[i])
    p += L[S]
    p %= mod

print(p)

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
P = 998244353

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

dp0 = [[0]*(S+1) for _ in range(N)]
dp1 = [[0]*(S+1) for _ in range(N)]
dp2 = [[0]*(S+1) for _ in range(N)]

dp0[0][0] = 1
dp1[0][0] = 1
if A[0] <= S:
    dp1[0][A[0]] = 1

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

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

Solution (Python):
import numpy as np

MOD = 998244353

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

dp = np.zeros((N+1, S+1), np.int64)
dp[:, 0] = 1
dp[1, 0] = 3
if As[0] <= S:
    dp[1, As[0]] = 1
for i in range(1, N):
    A = As[i]
    dp[i+1] += 2 * dp[i] - dp[i-1]
    dp[i+1, A:] += dp[i, :-A] - dp[i-1, :-A]
    dp[i+1] %= MOD

print(dp[N, S])

Solution (Python):
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math


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

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

print(ans)

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

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

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

print(ans)

Solution (Python):
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    import numpy as np

    mod = 998244353

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

    
    polynomial = np.zeros(S+1, int)
    ans = 0
    for i in A:
        polynomial[0] += 1
        polynomial[i:] += polynomial[:-i].copy()
        polynomial %= mod
        ans += polynomial[S]

    print(ans % mod)

main()

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))

def resolve():
    N,S=pin()
    A=tupin()
    mod=998244353

    
    
    
    

    
    
    
    
    
    
    
    
    
    
    

    from collections import defaultdict 
    from copy import deepcopy

    F=defaultdict(int)
    G=defaultdict(int)
    F[0]=1 
    
    
    for a in A:
        
        if len(G)==0:
            G[0]=1
            if a<=S:
                G[a]=1
        else:
            G[0]+=1
            temp=defaultdict(int)
            for g in G:
                temp[g]+=G[g]
                if g+a<=S:
                    temp[g+a]+=G[g]
                    temp[g+a]%=mod
            G=temp
            
        
        for g in G:
            F[g]+=G[g]
            F[g]%=mod
                    
    print(F[S])




resolve()

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

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

    dp1 = [0] * (S+1)
    dp2S = 0
    for A in As:
        dp2S += dp1[S]
        if S-A >= 0:
            dp2S += dp1[S-A]
        if S-A == 0:
            dp2S += 1
        dp2S %= MOD
        for sm in reversed(range(A+1, S+1)):
            dp1[sm] += dp1[sm-A]
            dp1[sm] %= MOD
        if S-A >= 0:
            dp1[A] += dp1[0] + 1
            dp1[A] %= MOD
        dp1[0] += 1

    print(dp2S)


solve()

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

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

    dp = [[0]*(3) for _ in range(S+1)]
    dp[0][0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp[sm][2] += dp[sm][1] + dp[sm][0]
            if sm-A >= 0:
                dp[sm][2] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][2] %= MOD
            dp[sm][1] += dp[sm][0]
            if sm-A >= 0:
                dp[sm][1] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][1] %= MOD

    print(dp[S][2])


solve()

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

Q = [0 for _ in range(S+1)]
ans = 0
for i in range(N):
  Q[0] += 1
  Q2 = [0 for _ in range(S+1)]
  for j in range(S+1):
    Q2[j] += Q[j]%MOD
    if j+A[i] <= S: 
      Q2[j+A[i]] += Q[j]%MOD
  Q = Q2
  ans += Q[S]%MOD
ans = ans %MOD
print(ans)

Solution (Python):
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
f=np.zeros(3001,int)

ans=0
for ai in a:
  ff=np.zeros(3001,int)
  ff+=f
  ff[ai:]+=f[:-ai]
  ff[0]+=1
  ff[ai]+=1
  f=ff
  f%=mod
  ans+=f[s]
  ans%=mod
print(ans)

Solution (Python):

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

mod = 998244353




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

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

for i in range(N):
    x = a[i]
    for j in range(S+1):
        if j > x:
            dp[i+1][j] = sumdp[i][j-x]
        elif j==x:
            dp[i+1][j] = i + 1 
        elif j < x:
            dp[i+1][j] = 0
    
        dp[i+1][j] %= mod
        sumdp[i+1][j] = sumdp[i][j]+dp[i+1][j]
        sumdp[i+1][j] %= mod

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

Solution (Python):
import numpy as np

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


f = np.zeros(s+1,int)

for i in a:
    f[0] += 1
    f[i:] += f[:-i].copy()
    f %= mod
    ans += f[s]

print(ans%mod)

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

dp=[[0]*(S+10) for i in range(N+1)]
for i in range(N):
    for j in range(S+1):
        dp[i+1][j]=dp[i][j]
        dp[i+1][j]+=dp[i][j-A[i]] if j>=A[i] else 0
        dp[i+1][j]+=1 if (j==A[i] or j==0) else 0
        dp[i+1][j]%=MOD
ans=0
for i in range(1,N+1):
    ans=(ans+dp[i][S])%MOD
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;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:
			if j==0:
				dp[i+1][a[i]]+=i+1
			else:
				dp[i+1][j+a[i]]+=dp[i][j]
				dp[i+1][j+a[i]]%=mod
		if j+a[i]==s:
			ans+=dp[i+1][j+a[i]]*(n-i)
			ans%=mod
print(ans)

Solution (Python):
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]
		dp1[i+1][j]+=dp0[i][j]+dp1[i][j]
		dp2[i+1][j]+=dp0[i][j]+dp1[i][j]+dp2[i][j]
		dp0[i+1][j]%=mod;dp1[i+1][j]%=mod;dp2[i+1][j]%=mod
		if j+a[i]<=s:
			dp1[i+1][j+a[i]]+=dp1[i][j]+dp0[i][j]
			dp2[i+1][j+a[i]]+=dp1[i][j]+dp0[i][j]
			dp1[i+1][j+a[i]]%=mod;dp2[i+1][j+a[i]]%=mod
print(dp2[n][s])