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:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md = 998244353
    n, s = MI()
    aa = LI()
    dp = [0] * (s + 1)
    ans = 0
    for a in aa:
        dp[0] += 1
        for i in range(s, a - 1, -1):dp[i] += dp[i - a]
        ans += dp[s]
    print(ans%md)

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    md = 998244353
    n, s = MI()
    aa = LI()
    dp = [0] * (s + 1)
    ans = 0
    for a in aa:
        dp[0] += 1
        for i in range(s, a - 1, -1):
            dp[i] += dp[i - a]
            dp[i] %= md
        ans += dp[s]
        ans %= md
    print(ans)

main()

Submission status: Accepted

Solution code:
import numpy as np

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

dp = np.zeros((s + 1, 3), dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()

    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)

Submission status: Accepted

Solution code:
n,s = map(int,input().split())
a = tuple(map(int,input().split()))

mod = 998244353

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

for i in range(1,n+1):
    a_t = a[i-1]
    for j in range(s+1):
        dp[i][j] = dp[i-1][j]
        if(j == 0)|(j == a_t):
            dp[i][j] += 1
        if(j >= a_t):
            dp[i][j] += dp[i-1][j-a_t]
        dp[i][j] %= mod

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

Submission status: Accepted

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

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

dp = np.array([[0] * 3 for _ in range(s + 1)], dtype=np.int64)
dp[0][0] = 1

for i, e in enumerate(a):
    cp = dp.copy()
    dp[:, 1] += cp[:, 0]
    dp[:, 2] += cp[:, 0] + cp[:, 1]

    dp[e:, 1] += cp[:-e, 0] + cp[:-e, 1]
    dp[e:, 2] += cp[:-e, 0] + cp[:-e, 1]

    dp %= mod

ans = dp[s][2]
print(ans)

Submission status: Accepted

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

def main():
    n,s = map(int,input().split())
    a = tuple(map(int,input().split()))

    mod = 998244353

    res = 0

    #dp[i][j]:a[i]まででf(L,?) = jとなるLの合計数
    dp = [[0]*3003 for i in range(n)]

    for i in range(n):
        if a[i] < s:
            res = (res+dp[i-1][s-a[i]]*(n-i))%mod
        elif a[i] == s:
            res = (res+(i+1)*(n-i))%mod
        for j in range(3003):
            if j < a[i]:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = (dp[i-1][j] + dp[i-1][j-a[i]])%mod
        dp[i][a[i]] += i+1
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
mod = 998244353
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
r = 0

for i in range(1, N+1):
    a = A[i-1]
    for j in range(1, 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
    r += dp[i][S]
print(r%mod)

Submission status: Accepted

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

for i in range(1, N+1):
    a = A[i-1]
    dp1[i][0] = 1
    for j in range(S+1):
        dp1[i][j] += dp1[i-1][j]
        if j == a:
            dp1[i][j] += 1
        if j-a >= 0:
            dp1[i][j] += dp1[i-1][j-a]
        dp1[i][j] %= mod
    r += dp1[i][S]
print(r%mod)

Submission status: Accepted

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

for i in range(1, N+1):
    a = A[i-1]
    dp1[i][0] = 1
    for j in range(S+1):
        dp1[i][j] += dp1[i-1][j]
        dp2[i][j] = dp2[i-1][j]
        if j == a:
            dp1[i][j] += 1
        if j-a >= 0:
            dp1[i][j] += dp1[i-1][j-a]
        dp2[i][j] += dp1[i][j]
        dp1[i][j] %= mod
        dp2[i][j] %= mod

print(dp2[-1][S])
#print(dp[1])
#print(dp[2])
#print(dp[3])

Submission status: Accepted

Solution code:
K = 32
P = 998244353
pa = (1 << 30) - ((1 << 30) % P)
M = []
N, S = map(int, input().split())
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = 1 << K * S
mmm = (1 << K) - 1
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += mm
    s += s >> a * K
    s -= ((s & m) >> 30) * pa
    ans += s & mmm

print(ans % P)

Submission status: Accepted

Solution code:
K = 32
P = 998244353
pa = (1 << 30) - ((1 << 30) % P)
M = []
N, S = map(int, input().split())
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = (1 << K * (S + 1)) - 1
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += s >> S * K

print(ans % P)

Submission status: Accepted

Solution code:
def f_knapsack_for_all_segments(MOD=998244353):
    # 参考: https://maspypy.com/atcoder-参加感想-2019-03-22abc-159
    import numpy as np
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    ans = 0
    f = np.zeros(S + 1, np.int64)  # f[k]: 多項式の x**k の項の係数
    for a in A:
        # f で表される多項式に対して (f + 1)(1 + x**a) を新しい f とする
        f[0] += 1  # f + 1
        f[a:] += f[:-a].copy()  # 1 + x**a を掛ける
        f %= MOD
        # x**S の項の係数を解に加える
        ans += f[S]
        ans %= MOD
    return ans

print(f_knapsack_for_all_segments())

Submission status: Accepted

Solution code:
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * 3001, 2)
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += (s >> S * K) & mmm

print(ans % P)

Submission status: Accepted

Solution code:
def setM():
    k = K2 // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m, ~m, (1 << K2 + k) % P))
        k //= 2
        break

def modp(n):
    for k, m, tm, a in M:
        n = (n & tm) + ((n & m) >> K2 + k) * a
    return n

K = 64
K2 = K // 2
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Submission status: Accepted

Solution code:
def setM():
    k = K2 // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m, ~m, (1 << K2 + k) % P))
        k //= 2

def modp(n):
    for k, m, tm, a in M:
        n = (n & tm) + ((n & m) >> K2 + k) * a
    return n

K = 64
K2 = K // 2
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Submission status: Accepted

Solution code:
mod = 998244353

n,s = map(int, input().split())
a = list(map(int, input().split()))
m = 3000
DP = [0]*(m+1)
ans = 0
for ai in a:
    DP[0] += 1
    for j in reversed(range(ai,m+1)):
        DP[j] += DP[j-ai]
        DP[j] %= mod
    ans += DP[s]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
def setM():
    K2 = K // 2
    k = K // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m))
        k //= 2

def modp(n):
    K2 = K // 2
    k = K // 2
    for k, m in M:
        n = (n & (~m)) + ((n & m) >> (K2 + k)) * ((1 << K2 + k) % P)
    return n

K = 64
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    ans = 0
    dp = [0]*(s+1)
    for i in range(n):
        ai = a[i]
        for j in range(s+1)[::-1]:
            nj = j+ai
            if nj > s:
                continue
            dp[nj] += dp[j]
            dp[nj] %= mod
        if ai <= s:
            dp[ai] += i+1
            dp[ai] %= mod
        ans += dp[s]
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, s = map(int, input().split())
a = [int(item) for item in input().split()]

dp = [[0] * (s+1) for _ in range(n)]
dp[0][0] = 1
if a[0] <= s:
    dp[0][a[0]] = 1
ans = 0
for i, item in enumerate(a[1:]):
    for j in range(s+1):
        # Not use item
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        # Do use item
        if j + item <= s:
            dp[i+1][j + item] += dp[i][j]
            dp[i+1][j + item] %= MOD
    # Start from i
    if item <= s:
        dp[i+1][item] += 1
    dp[i+1][0] += 1
    ans += dp[i+1][s]
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    ans = 0
    f = [0]*(s+1)
    f[0] = 0
    for i in a:
        f[0] += 1
        for j in range(s+1)[::-1]:
            nj = j+i
            if nj > s:
                continue
            f[nj] += f[j]
            f[nj] %= mod
        ans += f[s]
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from numpy import*
(n,s),a,m,e=map(int,input().split()),list(map(int,input().split())),998244353,3001;D=zeros((n,e));D[0][a[0]]=1
for j,i in enumerate(a[1:]):D[j+1,i]+=j+2;D[j+1,i:]+=D[j,:e-i];D[j+1,:]=(D[j+1,:]+D[j,:])%m
print(int(sum(D[:, s]) % m))

Submission status: Accepted

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

dp1 = [0]*(3001*N)
dp2 = [0]*(3001*N)

for n in range(N):
    for s in range(3000,-1,-1):
        dp2[n*N+s] = dp2[(n-1)*N+s]
        dp1[n*N+s] = dp1[(n-1)*N+s]
        if s>A[n]:
            dp2[n*N+s] += dp1[(n-1)*N+s-A[n]]*(N-n)
            dp1[n*N+s] += dp1[(n-1)*N+s-A[n]]
        elif s==A[n]:
            dp2[n*N+s] += (n+1)*(N-n)
            dp1[n*N+s] += n+1
        dp2[n*N+s] %= mod
        dp1[n*N+s] %= mod

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]


mod = 998244353
inf = 1e10

#solve
def solve():
    n, s = LI()
    a = LI()
    dp1 = [0] * (3000 + 1)
    dp2 = [0] * (3000 + 1)
    ans = 0

    for i in range(n):
        for j in range(s+1):
            dp2[j] = dp1[j]
        
        for j in range(a[i], s + 1):
            dp2[j] += dp1[j - a[i]]
            dp2[j] %= mod
        dp2[a[i]] += i + 1 
        ans += dp2[s]
        ans %= mod
        dp1 = dp2[::1]
        # print(dp2)
    print(ans)
            
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

ans = 0
tmp = [0]

for i, ai in enumerate(a):
    dpn = []
    dp[0] = i + 1
    for j in range(s+1):
        if j - ai >= 0 and dp[j-ai]:
            dpn.append((dp[j] + dp[j-ai]) % mod)
        else:
            dpn.append(dp[j])
    # print(dpn)
    ans = (ans + dpn[s]) % mod
    dp = dpn[:]
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)
ans = 0
for i in range(n):
    ndp = dp[:]
    if a[i] <= s:
        ndp[a[i]] = (ndp[a[i]] + i+1) % mod
    for j in range(s):
        if j+a[i] <= s:
            ndp[j+a[i]] = (ndp[j+a[i]] + dp[j]) % mod
    ans = (ans + ndp[s]) % mod
    dp = ndp[:]
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)
ans = 0
for i in range(N):
    ndp = dp[:]
    if A[i] <= S:
        ndp[A[i]] = (ndp[A[i]] + i+1) % mod
    for j in range(S):
        if j+A[i] <= S:
            ndp[j+A[i]] = (ndp[j+A[i]] + dp[j]) % mod
    ans = (ans + ndp[S]) % mod
    dp = ndp[:]
print (ans)

Submission status: Accepted

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

Submission status: Accepted

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

import numpy as np
MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
F = np.zeros(s+1, dtype=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:
def main():
    import sys
    input = sys.stdin.readline

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

    dp = [[0] * (S+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(S+1):
            dp[i+1][j] = (dp[i+1][j] + dp[i][j])%mod
            if j+a <= S:
                tmp = 1
                if j == 0:
                    tmp *= (i+1)
                if j+a == S:
                    tmp *= (N-i)
                dp[i+1][j+a] = (dp[i+1][j+a] + (dp[i][j] * tmp)%mod)%mod
    print(dp[-1][S])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    mod=998244353
    n,s=map(int,input().split())
    A=tuple(map(int,input().split()))
    DP=[[x+1]+[0]*s for x in range(n+1)]
    for i,a in enumerate(A):
        for j in range(1,s+1):
            if j-a<0:
                DP[i+1][j]=DP[i][j]
            else:
                DP[i+1][j]=DP[i][j]+DP[i][j-a]
            DP[i+1][j]%=mod
    ans=0
    for dp in DP:
        ans+=dp[-1]
        ans%=mod
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

d = [[0 for _ in range(2)] for _ in range(s+1)]
mod = 998244353

for i in range(n):
    for j in reversed(range(s-a[i]+1)):
        d[j + a[i]][0] += d[j][0]
        d[j + a[i]][1] += d[j][0] * (n - i)
        d[j + a[i]][0] %= mod
        d[j + a[i]][1] %= mod
    if a[i] <= s:
        d[a[i]][0] += i + 1
        d[a[i]][1] += (i + 1) * (n - i)
        d[a[i]][0] %= mod
        d[a[i]][0] %= mod

print(d[s][1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0]*(3001) for _ in range(3001)]
# dp[i][j] は i 番目までを使った時に、どれだけの組み合わせがあり、かける必要があるか？
ans = 0
mod = 998244353
for i in range(n):
    dp[i][a[i]] = i+1
    if a[i] == s:
        ans += (i+1)*(n-i) %mod
for i in range(0,n):
    for j in range(s+1):
        if j > a[i]:
            dp[i][j] += dp[i-1][j] + dp[i-1][j-a[i]]
            dp[i][j] %= mod
            if j == s:
                ans += dp[i-1][j-a[i]] * (n-i)
                ans %= mod
                #print(ans,i,j)
        else:
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
print(ans%mod)

Submission status: Accepted

Solution code:
N, S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
MOD =   998244353
DP = [[0 for p in range(S+1)]for x in range(N)]
ans = N * (A[0]==S)
if A[0]<=S:
    DP[0][A[0]] = 1
for n,a in enumerate(A):
    if n!=0:
        #もらう
        for p in range(a,S+1):
            DP[n][p] += DP[n-1][p-a]
        for p in range(S+1):
            DP[n][p] += DP[n-1][p]
            DP[n][p] %= MOD
        #初期化
        if a<=S:DP[n][a] += n+1
    ans += (DP[n][S]*(N-n))% MOD
    DP[n][S] = 0
    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 i in range(n+1)]
for i in range(n):
  dp[i][0] = 1
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]:
      dp[i+1][j] += dp[i][j-a[i]]
      dp[i+1][j] %= mod
ans = list()
for i in dp:
  ans.append(i[-1])
ans = ans[1:]
print(sum(ans)%mod)

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = [int(i) for i in input().split()]

mod = 998244353

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

ret = 0
for i, a in enumerate(A) :
  if a <= S :
    dp[i + 1][a] += i + 1
    
  for j in range(S, -1, -1) :
    dp[i + 1][j] += dp[i][j]
    if j >= a :
      dp[i + 1][j] += dp[i][j - a]
    dp[i + 1][j] %= mod
        
  ret += (dp[i + 1][S] - dp[i][S]) * (N - i) % mod
  ret %= mod

print(ret)

Submission status: Accepted

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

mod = 998244353
dp = [[0] * n for _ in range(3000 + 1)]
dp[a[0]][0] = 1

for i in range(1, s + 1):
    for j in range(1, n):
        if i == a[j]:
            dp[i][j] = dp[i][j-1] + j + 1
        elif i - a[j] > 0:
            dp[i][j] = dp[i][j-1] + dp[i - a[j]][j - 1]
        else:
            dp[i][j] = dp[i][j-1]

        dp[i][j] %= mod

print(sum([dp[s][j] for j in range(n)]) % mod)

Submission status: Accepted

Solution code:
n,s = map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
rui = []
now = 0
pl = []
for i in range(n):
    now += a[i]
    rui.append(now)
l = [[0 for i in range(s)] for i in range(n)]
ans = 0
for i in range(n):
    if a[i] < s:
        l[i][a[i]] += i+1
        l[i][a[i]] %= mod
    elif a[i] == s:
        ans += i*(n-i-1)
        ans += n
        ans %= mod
    for j in range(s):
        if i > 0:
            if l[i-1][j] > 0:
                if j+a[i] < s:
                    l[i][j+a[i]] += l[i-1][j]
                    l[i][j+a[i]] %= mod
                elif j+a[i] == s:
                    ans += l[i-1][j]*(n-i)
                    ans %= mod
                l[i][j] += l[i-1][j]
                l[i][j] %= mod
print(ans)

Submission status: Accepted

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

mod = 998244353

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

# init
dp[a[0]][0] = 1

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



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

print(ans % mod)

Submission status: Accepted

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


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

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

dp = [[0 for i in range(6002)]for j in range(n+1)]
ans = 0
for i in range(n):
    now = a[i]
    dp[i+1][now] = i+1
    for jj in range(s-1):
        j = jj+1
        dp[i+1][j] += dp[i][j]
        dp[i+1][j+now] += dp[i][j]
        dp[i+1][j] %= 998244353
    ans += dp[i+1][s] * (n - i)
    ans %= 998244353
    #print(ans)


print(ans)

Submission status: Accepted

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[k + 1] + [0] * s for k in range(n + 1)] #dp[i][j] : 左からi個使ってぴったりj
for i in range(1, n + 1):
    for j in range(1, s + 1):
        if j - a[i - 1] < 0:
            dp[i][j] = dp[i - 1][j] % 998244353
        else:
            dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - a[i - 1]]) % 998244353
ans = 0
for i in range(1, n + 1):
    ans += dp[i][s]
    ans %= 998244353
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

from collections import Counter

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n, s = [int(s) for s in input().strip().split()]
    A = [int(s) for s in input().strip().split()]

    M = 998244353
    dp = Counter()
    dp[0] = 1
    result = 0
    for a in A:
        dp2 = Counter(dp)
        dp2[0] += 1
        for k, v in dp.items():
            if k + a <= s:
                dp2[k + a] = (dp2[k + a] + dp[k]) % M
        dp = dp2
        # print(dp)
        result = (result + dp[s]) % M
    print(result)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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(1, n+1):
    for j in range(1, s+1):
        if a[i-1] > j:
            dp[i][j] = dp[i-1][j]
        elif a[i-1] == j:
            dp[i][j] = (dp[i-1][j] + i)%998244353
        else:
            dp[i][j] = (dp[i-1][j] + dp[i-1][j-a[i-1]])%998244353

ans = 0

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


print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inpl(): return list(map(int, sys.stdin.readline().split()))


def inpl_str(): return list(sys.stdin.readline().split())


N, S = inpl()
aa = inpl()

dp = [0 for _ in range(3010)]
dp[0] = 0

ans = 0
for i, a in enumerate(aa):

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

    for s in reversed(range(a, S)):
        if s == a:
            dp[s] += i+1
        else:
            dp[s] += dp[s-a]
        dp[s] %= mod


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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 998244353

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,S = LI()
A = LI()

d = defaultdict(int)
ans = 0
for i in range(N):
    temp = defaultdict(int)
    for k,v in d.items():
        temp[k] = v
    ans += d[S-A[i]]*(N-i)
    if S == A[i]:
        ans += (i+1)*(N-i)
    ans %= mod
    d[A[i]] += i+1
    for k in range(A[i]+1,3001):
        d[k] += temp[k-A[i]]
    #print(i,ans,d)
print(ans)

Submission status: Accepted

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