Problem:


Score : 600 points

Problem Statement

Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.

For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:

f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq S \leq 3000

1 \leq A_i \leq 3000

Input

Input is given from Standard Input in the following format:

N S
A_1 A_2 ... A_N

Output

Print the sum of f(L, R), modulo 998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

5

The value of f(L, R) for each pair is as follows, for a total of 5.

f(1,1) = 0

f(1,2) = 1 (for the sequence (1, 2))

f(1,3) = 2 (for (1, 2) and (3))

f(2,2) = 0

f(2,3) = 1 (for (3))

f(3,3) = 1 (for (3))

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

152



Sample input:
3 4
2 2 4


Sample output:
5

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import copy

r = 998244353

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

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

# s => comb
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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
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)

Submission status: Accepted

Solution code:
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): #Lのみ定めたdp1
	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): #L, Rを定めたdp2
	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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 998244353

# N,S,A <= 3000

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):
    #print(DP)
    #print(ans)
    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(DP)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# a
# b + ab
# c + bc + abc
# (1+x)
# (1+x)(1+x) + (1+x) = 2 + 3 + 1
# (1+x)(1+x)(1+x) + (1+x)(1+x) + (1+x) = 3 +

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11139734

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

Submission status: Accepted

Solution code:
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):
    
    # x[i] を加えない場合
    m[:,0] = p[:,0]
    m[:,1] = p[:,0] + p[:,1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
    m[:,2] = p[:,0] + p[:,1] + p[:,2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

    # x[i] を加える場合
    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]))

Submission status: Accepted

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

Submission status: Accepted

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

# dp[i][s] : Rをiに固定した時に、和がsとなる整数列の組が何回現れるか
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)

Submission status: Accepted

Solution code:
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(sum_array, ans)
print(ans)

Submission status: Accepted

Solution code:
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      # Lがiからを足す
    next_dp = [0]*(S+1)
    for j in range(S+1):
        next_dp[j] += dp[j]             # A[i]を選ばない
        next_dp[j] %= MOD
        if j+A[i]<=S:
            next_dp[j+A[i]] += dp[j]    # A[i]を選ぶ
            next_dp[j+A[i]] %= MOD
    dp = next_dp
    ans += dp[S]    # Rがiまでを足す
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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]
            # print(dp)
        dp %= mod
        ans = (ans + dp[-1]) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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(fwd_acc)
    # print(ans)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

  # サンプル3 4 2,2,4の場合、P1=1+x^2,P2=1+x^2,P3=1+x^4とすると、解は
  # P1P2P3+P1P2+P2P3+P1P3+P1+P2+P3におけるx^4の係数となる。
  # Q1=P1,Q2=P2+P1P2,Q3=P3+P2P3+P1P2P3とすると、
  # P1P2P3+P1P2+P2P3+P1P3+P1+P2+P3=Q1+Q2+Q3
  # Q1=P1(1+0)
  # Q2=P2(1+Q1)
  # Q3=P3(1+Q2)
  # 今のQに1を足してからPを掛けて、次のQを求める。
  # 解は、それぞれのQのx^4の係数を足していけばよい。
  ans = 0
  q = [0 for _ in range(S+1)]
  for i in range(len(A)):
    q[0] += 1
    q[0] %= MOD
    q2 = q[:]
    for j in range(S):
      if j+A[i] <= S:
        q2[j+A[i]] += q[j]
        q2[j+A[i]] %= MOD
    q = q2[:]
    ans += q[S]
  #print(q)
  print(ans%MOD)
  
main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
mod = 998244353


N, S, *A = map(int, open(0).read().split())

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

    ans += dp[-1]
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

MOD = 998244353
N, S = lr()
A = lr()
dp = np.zeros(S+1, np.int64)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    dp[a:] += prev[:-a]
    dp %= MOD
    answer += dp[-1] # その位置をRとした時

print(answer % MOD)
# 26

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

MOD = 998244353
N, S = lr()
A = lr()
dp = np.array([0] * (S+1), dtype=np.int64)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    dp[a:] += prev[:-a]
    answer += dp[-1] # その位置をRとした時
    dp %= MOD

print(answer % MOD)
# 26

Submission status: Accepted

Solution code:
import sys

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

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp[:]
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置をRとした時

print(answer % MOD)
# 26

Submission status: Accepted

Solution code:
import sys

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

MOD = 998244353
N, S = lr()
A = lr()
dp = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N,S =map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
ans=0
q=[0]*(S+1)
for i in range(N):
    q2=q.copy()
    if A[i]<=S:
        for j in range(A[i],S+1):
            q[j]+=q2[j-A[i]]
        q[A[i]]+=i+1
    ans+=q[S]
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def main():
	n, s, *a = map(int, open(0).read().split())
	ans = 0
	mod = 998244353
	dp = [0] * (s + 1)
	for i, x in enumerate(a):
		dp[0] += 1
		if x > s:continue
		ans += dp[s - x] * (n - i)
		ans %= mod
		dp = dp[:x] + [(dp[j] + dp[j - x]) % mod for j in range(x, s + 1)]
	print(ans)
	
if __name__=="__main__":
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    n,s = map(int,input().split())
    A = list(map(int,input().split()))
    dp = [[0 for j in range(s+1)] for i in range(n+1)]

    mod = 998244353

    ans = 0

    dp[0][0] = 1

    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
    
    print(ans%mod)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
#d = sum(A)
mod = 998244353

"""
多項式係数を使った数え上げでリベンジしてみる。
maspyさんのを参考に実装する。

（注意）多項式係数全てを書き下すと、d = sum(A)次式になるが、
これは Ai*N = 3000*3000 次になりTLEする。。。
S次の項までで打ち切る事を忘れない事。

やってみてわかったけど、実装自体はdpでやったのとほぼ同じ。
多項式係数を使う方法は実質flexibleなdpということ？
"""

f = [0] * (1 + S) # f[i] = (coefficient of degree i)
ans = 0

for i in range(N):
    g = [0] * (1 + S) # g = (1 + f) * (1 + x^{A[i]})
    f[0] += 1
    for j in range(1 + S):
        if j - A[i] < 0:
            g[j] = f[j]
        else:
            g[j] = f[j] + f[j - A[i]]
    ans += g[S]
    ans %= mod
    f = g

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = [0] + list(map(int, input().split()))
mod = 998244353

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

"""
dp[i][j] = (i個までの数を使ってj点とる組み合わせ)
としたはいいが、f(L, R)をf(1,L)とf(1, R)に分解できずに爆死したのが敗因。

各(L, R)に対してdpするとTLEになるから手詰まりになると思ったわけだけど、
上のdpテーブルを各iに対して使い回しつつ、新たなdpテーブル[1, 0, 0, ...]を
作成して「元のdpテーブルに加算しておけば」dpテーブル一個で1番目スタート、2番目スタート、
..., L番目スタートのdpテーブル全てを考えられる！
（解説放送前半を参考）
"""

# i == 0の時
dp[0] = 1
ans = 0

# i >= 1の時
for i in range(1, N + 1):
    for j in range(S + 1):
        if j - A[i] < 0:
            dp2[j] = dp[j]
        else:
            dp2[j] = dp[j] + dp[j - A[i]]
    ans += dp2[S]
    ans %= mod

    dp = dp2 # deepcopyしなくてもこれで十分なはずだし、ポインタ渡しなので高速？
    dp[0] += 1
    dp2 = [0] * (S + 1)

print(ans)

Submission status: Accepted

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

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, a in enumerate(A):
    dp[i+1][0] = i+2
    for s in range(1, S+1):
        if s-a >= 0:
            dp[i+1][s] = (dp[i][s] + dp[i][s-a]) % mod
        else:
            dp[i+1][s] = dp[i][s]

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

print(ans)

Submission status: Accepted

Solution code:
def main():
  import sys
  read = sys.stdin.buffer.read
  r = 998244353
  U, S, *A = map(int, read().split())
  import copy
  ans = 0
  f = [0]*3010
  for a in A:
      c = copy.copy(f)
      f = [0]*a+c[:-a]
      f = [x+y for x,y in zip(f,c)]
      f[0] += 1
      f[a] += 1
      ans += f[S]
  ans %= r
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

DP=[0]*(S+1)

# 多項式の考え方が分かりやすい.
# 多項式を使わないなら,
# DP[j] := 終端がiになる区間について, S=jのときのF(*,i)の和
# を更新していくと考えれば良いのかな...

DP[0]=1
ANS=0
for a in A:
    for i in range(S-a,-1,-1):
        DP[i+a]+=DP[i]
    DP[0]+=1
    ANS+=DP[S]
    
print(ANS%mod)

Submission status: Accepted

Solution code:
def examA():
    N, M = LI()
    ans = N*(N-1)//2 + M*(M-1)//2
    print(ans)
    return

def examB():
    def judge(A):
        #print(A)
        n = len(A)
        for i in range(n//2):
            if A[i]!=A[n-i-1]:
                return False
        return True
    S = SI()
    N = len(S)
    if not judge(S):
        print("No")
        return
    if judge(S[:(N-1)//2]) and judge(S[(N+1)//2:]):
        print("Yes")
    else:
        print("No")
    return

def examC():
    L = I()
    ans = (L/3)**3
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(bool)
    C = Counter(A)
    M = 0
    for key,c in C.items():
        M += c*(c-1)//2
    #print(C)
    #print(M)
    ans = [0]*N
    for i in range(N):
        a = A[i]
        c = C[a]
        ans[i] = M -(c*(c-1)//2) + ((c-1)*(c-2)//2)
    for v in ans:
        print(v)
    return

def examE():
    H, W, K = LI()
    S = [SI()for _ in range(H)]
    SH = [[0] * (W + 1) for _ in range(H + 1)]
    for i in range(H):
        now = 0
        for j in range(W):
            now += int(S[i][j])
            SH[i + 1][j + 1] = SH[i][j + 1] + now

    def calc(a,b,c,d):
        return SH[c][d] - SH[a][d] - SH[c][b] + SH[a][b]

    ans = H+W-2
    mask = 2**(H-1)-1
    for i in range(mask+1):
        cut = [0]
        cur = 0
        for j in range(H-1):
            if i&(1<<j)==(1<<j):
                cut.append(j+1)
                cur += 1
        cut.append(H)
        L = [0]*(len(cut)-1)
        flag = True
        for w in range(W):
            now_L = [0]*(len(cut)-1)
            for s in range(len(cut) - 1):
                n = calc(cut[s], w, cut[s + 1], w + 1)
                now_L[s] = n
                if n+L[s]> K:
                    if n>K:
                        flag = False
                        cur = inf
                        break
                    cur += 1
                    L = [0] * (len(cut))
            if not flag:
                break
            for s in range(len(cut) - 1):
                L[s] += now_L[s]
        if not flag:
            continue
        ans = min(ans,cur)

    print(ans)
    return
"""
2 1 1
1
1
"""# 1

def examF():
    N, S = LI()
    A = LI()
    dp = [[0]*(S+1) for _ in range(N+1)]
    for i in range(N):
        dp[i][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(S+1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod2
            if j+a<=S:
                dp[i+1][j+a] += dp[i][j]
                dp[i+1][j+a] %= mod2
    ans = 0
    for i in range(N+1):
        ans += dp[i][S]
        ans %= mod2
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF()

"""

"""