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 = map(int, input().split())
a = list(map(int, input().split()))
modval = 998244353

def update(newval, length_elems):
  # sequences made up of only the new value
  if newval<= s:
    new_state[newval][0] = length_elems
    new_state[newval][1] = length_elems
  # appending to existing sequences
  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

# [[combos without R, combos with R] that add to a given target]
old_state = [[0, 0] for _ in range(s+1)]
for i, newval in enumerate(a, 1):
  # reset the new state to zeros
  new_state = [[0, 0] for _ in range(s+1)]
  # create new state from old state
  update(newval, i)
  # old state now point to new state
  old_state = new_state
print(new_state[s][1]%modval)

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
            # dp[n][s]: n個目で和がちょうどsになるインデックスの組における
            #           L のパターン数
            v = dp[n - 1][s]
            if s - a >= 0:
                v += dp[n - 1][s - a]
            dp[n][s] = v % MOD
        if S - a >= 0:
            # n個目で和がちょうどSになる時にRのパターン数をかけておく
            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()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
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 # and False
BIG = 10**18
#R = 10**9 + 7
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)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

#             dp[i + 1][s][0] = (dp[i + 1][s][0] + dp[i][s][0]) % MOD
#             dp[i + 1][s][1] = (dp[i + 1][s][1]
#                                + dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD
#             dp[i + 1][s][2] = (dp[i + 1][s][2]
#                                + dp[i][s][2] +
#                                dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD

#     for i, x in enumerate(A):
#         dp[i + 1][0][0] = dp[i][0][0]
#         for s in range(S, -1, -1):
#             dp[i + 1][s][1] = (dp[i][s][1] + dp[i][s][0]) % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0]) % MOD
#
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#         dp[i + 1][0][0] = dp[i][0][0]
#         dp[i + 1][0][1] = (dp[i][0][1] + dp[i][0][0]) % MOD
#         dp[i + 1][0][2] = (dp[i][0][2] + dp[i][0][1] + dp[i][0][0]) % MOD
#         for s in range(S, 0, -1):
#             dp[i + 1][s][1] = dp[i][s][1] % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1]) % MOD
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#     for x in A:
#         for s in range(S, 0, -1):
#             dp[s][1] += dp[s][0]
#             if s - x >= 0:
#                 v = dp[s - x][0] + (1 if s - x == 0 else 0)
#                 dp[s][0] += v
#                 dp[s][1] += v
#             dp[s][0] %= MOD
#             dp[s][1] %= MOD
#         dp[0][0] += 1
#         dp[0][1] += (dp[0][0] + 1)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# MOD = 10 ** 9 + 7
MOD = 998244353
# sys.setrecursionlimit(10**8)

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
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))
#%%code
def resolve():
    N,S=pin()
    A=tupin()#調子にのるな
    mod=998244353

    #形式的冪級数を考える
    #普通の部分和ッ->集合内の各アイテムについて、選ぶか選ばないか。O(2^n)の探索
    #これを形式的冪級数でいえば、（1+x^a）を掛ける計算になる　指数時間ではない
    #つまり、集合A,Sに対して、[x^s]PI(1+x^a_i) (ひだりのカッコ部分をf_iとする)

    #次に、Aの部分集合、じゃなくて問題の区間について考える (ABC169と異なる部分はここ)
    #サンプル1の場合。区間に含まれるのは…って考える前に
    #区間なので終点があるね、a3が追加されることで終点にf3がある区間が追加されるよね
    #じゃあこれももしかしたら漸化式で作れるかも
    #F0=f0=1,F1=1+f1,F2=1+f1f2+f1+f2,F3=1+f1f2f3+f1f2+f1+f2f3+f2+f3...
    #F2=f2(f1+1)+f1+1 ,F3=f3(f1f2+f2+1)+f1f2+f1+f2+1=f3(f1f2+f2+1)+f2(f1+1)+f1+1
    #えっこれ漸化式の和？G3=f3(f1f2+f2+1)みたいに終点ごとにわける
    #G3=f3(f2(f1+1)+1)=f3(G2+1),G2=f2(f1+1)=f2(G1+1) Gn=fn(1+Gn-1)=(1+x^a)(1+Gn-1)
    #F3=G3+G2+G1=f2(G2+1)+G2+G1,
    #Fn+1-Fn=fn+1*(1+Gn)=(1+x^a_(n+1))*(1+Gn)=Gn+1=(1+x^a)(1+Gn)
    #FもGも漸化式で求められることがわかりました（？）

    from collections import defaultdict #本当は良くないがわかりやすさのためココに置く
    from copy import deepcopy

    F=defaultdict(int)
    G=defaultdict(int)
    F[0]=1 #init
    #F1-F0=f1*(1+G0)=f1+1
    #print(ans)
    for a in A:
        #G
        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
            
        #Fの計算
        for g in G:
            F[g]+=G[g]
            F[g]%=mod
                    #print(F)
    print(F[S])



#%%submit!
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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: #(1+x^A[i])をかけてもx^sを超えないときに限り。
      Q2[j+A[i]] += Q[j]%MOD
  Q = Q2
  ans += Q[S]%MOD
ans = ans %MOD
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
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)

Submission status: Accepted

Solution code:
# Knapsack for all segments
N, S = map(int, input().split())
a = list(map(int, input().split()))

mod = 998244353

# dp[x][s] = 最後にとるのが x に対しての部分和がsになる物の総数
#sumdp[x][s]= 最後に撮るのがx番目いぜんに対しての部分和がsになる物の総数

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

    MOD = 998244353

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

    # dp[i][j] : i番目の要素が右端である区間のうち，和がjになる整数列を持つ区間の個数
    for i, a in enumerate(A):            
        for j in range(S+1):
            if j == a:
                dp[i+1][j] += dp[i][j] + i + 1
                dp[i+1][j] %= MOD
            elif j > a:
                dp[i+1][j] += dp[i][j] + dp[i][j-a]
                dp[i+1][j] %= MOD
            else:
                dp[i+1][j] += dp[i][j]
                dp[i+1][j] %= MOD

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# F - Knapsack for All Segments
# https://atcoder.jp/contests/abc159/tasks/abc159_f

MOD = 998244353

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

# dp[i][j] = i 番目までの選択をして、1 つめの選択肢を選んだ k に対する ak の和が j であるような場合の数
dp = [[0] * (s + 1) for _ in range(n + 1)]

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

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

# f(h,i,C)を h <= x_1 < … < x_k <= i かつ A_(x_1) + … + A_(x_k) = C を満たす(x_1,…,x_k)の組の個数とする
# そして F(i,C) = f(1,i,C) + … + f(i,i,C) と定める
# 求めたい値は、F(1,S) + … + F(N,S) である
# すると(大体) F(i,C) = F(i-1,C-A_i) + F(i-1,C) + f(i,i,C) が成り立つ 
# dp[i][C] = F(i,C) としてdpする

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

count %= MOD
print(count)

Submission status: Accepted

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

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

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

ans = 0

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

print(ans)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 998244353  # type: int

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

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

print(dp1[n][s])

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

if __name__ == '__main__':
    main()