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()))
mod=998244353
dp00=[0]*(s+1)
dp01=[0]*(s+1)
dp10=[0]*(s+1)
dp11=[0]*(s+1)
dp20=[0]*(s+1)
dp21=[0]*(s+1)
dp00[0]=1
for i in range(n):
  for j in range(s+1):
    if i%2==0:
      if j>=a[i]:
        dp11[j]=(dp00[j-a[i]]+dp10[j-a[i]]+dp00[j]+dp10[j])%mod
        dp21[j]=(dp00[j-a[i]]+dp10[j-a[i]]+dp00[j]+dp10[j]+dp20[j])%mod
      else:
        dp01[j]=dp00[j]%mod
        dp11[j]=(dp00[j]+dp10[j])%mod
        dp21[j]=(dp00[j]+dp10[j]+dp20[j])%mod
    else:
      if j>=a[i]:
        dp10[j]=(dp01[j-a[i]]+dp11[j-a[i]]+dp01[j]+dp11[j])%mod
        dp20[j]=(dp01[j-a[i]]+dp11[j-a[i]]+dp01[j]+dp11[j]+dp21[j])%mod
      else:
        dp00[j]=dp01[j]%mod
        dp10[j]=(dp01[j]+dp11[j])%mod
        dp20[j]=(dp01[j]+dp11[j]+dp21[j])%mod
if n%2==1:
  print(dp21[s])
else:
  print(dp20[s])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp0=[[0 for i in range(s+1)] for j in range(n+1)]
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)]
dp0[0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp1[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j-a[i]]+dp1[i][j-a[i]]+dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
    else:
      dp0[i+1][j]=dp0[i][j]%mod
      dp1[i+1][j]=(dp0[i][j]+dp1[i][j])%mod
      dp2[i+1][j]=(dp0[i][j]+dp1[i][j]+dp2[i][j])%mod
print(dp2[n][s])

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353

dp=[0 for n in range(3001)]
c=0
for n in range(N):
    a=A[n]
    for s in range(0,S+1)[::-1]:
        if s+a<=S:
            dp[s+a]+=dp[s]
            dp[s+a]%=mod

    dp[a]+=n+1
    dp[a]%=mod
    c+=dp[S]
    c%=mod
#print(dp[S])
print(c)

Submission status: Accepted

Solution code:
#!python3

import numpy as np

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

MOD = 998244353


def add_elements(w, i):
    a = A[i]
    w[a:] += w[:-a].copy()
    if a <= S:
        w[a] += i + 1
    w %= MOD


def main():
    w = np.zeros(S + 1, dtype=int)
    ans = 0
    for i in range(N):
        add_elements(w, i)
        ans = (ans + w[S]) % MOD
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for i, a in enumerate(A):
    dp[0] +=1
    if a > S:
        continue

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

    for j, x in enumerate(dp[:S-a]):
        dp[j+a] += x
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    N, S = map(int, sysread().split())
    A = [0]+ list(map(int,sysread().split()))
    dp = [[0] * (S+1) for _ in range(N+1)]
    if A[1] <= S:
        dp[1][A[1]] = 1
    mod = 998244353
    for r in range(1, N):
        if A[r+1] <= S:
            dp[r+1][A[r+1]] += r+1
            dp[r + 1][A[r + 1]] %= mod
        for s in range(1,S+1):
            dp[r+1][s] += dp[r][s] + dp[r][s] - dp[r-1][s]
            dp[r+1][s] %= mod
            if s + A[r+1] <= S:
                dp[r+1][s+A[r+1]] += dp[r][s] - dp[r-1][s]
                dp[r + 1][s + A[r + 1]] %= mod
    print(dp[N][S] % mod)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
def main():
    mod=998244353
    n,s=map(int,input().split())
    a=list(map(int, input().split()))
    dp=[0]*(s+1)
    ans=0
    for i,x in enumerate(a):
        dp[0]+=1
        if x>s:
            continue
        ans=(ans+dp[s-x]*(n-i))%mod
        for k in range(s-1,x-1,-1):
            dp[k]=(dp[k]+dp[k-x])%mod
    print(ans)
    
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)]

mod = 998244353
# dp[i][s] A[i]まで見た時、合計sになる数。
# 各々の地点で新しく開始されるものも有るので毎回dp[i][0]は＋1
dp[0][0] = 1
ans = 0
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
    dp[ni][0] += 1
    ans += dp[ni][s]
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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

N, S = lr()
A = lr()
MOD = 998244353
dp = [0] * (S+1)

answer = 0
for a in A:
    dp[0] += 1
    for x in range(S, a-1, -1):
        dp[x] += dp[x-a]
    answer += dp[-1]
    answer %= MOD

print(answer%MOD)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, s = map(int, input().split())
    dp = [0] * (s + 1)
    res = 0
    for a in map(int, input().split()):
        dp[0] += 1
        for i in range(s - a, -1, -1):
            dp[i + a] += dp[i]
            if dp[i + a] >= MOD:
                dp[i + a] -= MOD
        res += dp[s]
        if res >= MOD:
            res -= MOD

    print(res)
resolve()

Submission status: Accepted

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        dp[0] +=1
        if a > S:
            continue

        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    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
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        dp[0] = i+1
        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, S = (int(i) for i in input().split())
    A = [int(i) for i in 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 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 = sum(dp[i][S] for i in range(N+1)) % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353


def main():
    N, S = (int(i) for i in input().split())
    A = [int(i) for i in 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 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 = 0
    for i in range(N+1):
        ans += dp[i][S]
        ans %= MOD
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 998244353


def main():
    N, S = (int(i) for i in input().split())
    A = [int(i) for i in 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 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 = 0
    for i in range(N+1):
        ans += dp[i][S]
    print(ans % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
U = 3001

ans = 0
dp = np.zeros(U, dtype=np.int64)
dp[0] = 1

for a in A:
    newDP = np.copy(dp)
    newDP[a:] += dp[:-a]
    newDP[0] += 1
    newDP %= mod
    dp = newDP

    ans += dp[S]
    ans %= mod

print(ans)

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)
for l in range(N):
  r = N - l
  x = a[l]
  if x > S: continue
  for i in range(S, 0, -1):
    if i + x > S: continue
    if i + x == S:
      dp[S] += dp[i] * r
      dp[S] %= mod
    else:
      dp[i + x] += dp[i]
      dp[i + x] %= mod
  if x == S:
    dp[S] += (l + 1) * r
    dp[S] %= mod
  else:
    dp[x] += l + 1
    dp[x] %= mod
  #print(dp)
print(dp[-1])

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): 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 LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,S = MI()
A = LI()
dp = FILL2(0,N+1,S+1)
for i in range(N):
    for j in range(S+1):
        if j>0 and j+A[i]<=S:
            dp[i+1][j+A[i]] += dp[i][j]
            dp[i+1][j+A[i]] %= MOD
        elif j==0 and A[i]<=S:
            dp[i+1][A[i]] += i+1
            dp[i+1][A[i]] %= MOD
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
ans = 0
for i in range(N+1):
    ans += dp[i][S]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
def input(): return sys.stdin.readline().rstrip()

def main():
    N,S=map(int,input().split())
    A=list(map(int,input().split()))
    dp0=[[0 if i!=0 else 1 for i in range(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)]
    for i in range(N):
        for j in range(S+1):
            b=int(j==0)
            dp1[i+1][j]+=dp1[i][j]+b
            dp2[i+1][j]+=dp1[i][j]+dp2[i][j]+b
            dp1[i+1][j]%=MOD
            dp2[i+1][j]%=MOD
            if j+A[i]<=S:
                dp1[i+1][j+A[i]]+=dp1[i][j]+b
                dp2[i+1][j+A[i]]+=dp1[i][j]+b
                dp1[i+1][j+A[i]]%=MOD
                dp2[i+1][j+A[i]]%=MOD
    print(dp2[-1][-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.buffer.readline


def read_int_n():
    return list(map(int, input().split()))


def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


@mt
def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))


if __name__ == '__main__':
    main()

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

    ans = 0
    dp = [0] * (S + 1)
    for i, a in enumerate(A, start=1):
        dp[0] = i  # i以前の(i+1)通りの起点がある（以後未取得）
        ans += dp[S]  # aを取らずにclose
        if S >= a:
            ans += dp[S - a]  # aを取ってclose
        ans %= MOD
        for s in reversed(range(a, S + 1)):
            dp[s] += dp[s - a]
            dp[s] %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
import random

# sys.stdin = open('input')

def inp():
    re = map(int, raw_input().split())
    if len(re) == 1:
        return re[0]
    return re

def inst():
    return raw_input().strip()

def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x

def my_main():
        n, s = inp()
        da = inp()
        dp = [[0 for i in range(s+1)] for i in range(n+1)]
        sm = [0 for i in range(s+1)]
        dp[0][0] = sm[0] = 1
        mod = 998244353
        for i in range(1, n+1):
            now = da[i-1]
            dp[i][0] = 1
            for j in range(s+1):
                if j>=now:
                    dp[i][j] += sm[j-now]
                dp[i][j] %= mod
            for j in range(s+1):
                sm[j] += dp[i][j]
                sm[j] %= mod
        ans = 0
        for i in range(n+1):
            ans += dp[i][s]*(n-i+1)
            ans %= mod
        print ans



my_main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353
    N,S=MI()
    A=LI()
    
    dp=[[0]*(S+1)for _ in range(N+1)]
    #dp[i][j]はi番目まで見た時に和がjになる組み合わせを何通り作れるか．
    #ただし，iを増やすたびにj=0が1つ増える（Lがひとつずれたものと対応）
    
    for i in range(N):
        a=A[i]
        dp[i][0]+=1
        for j in range(S+1):
            dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod
            if j+a<=S:
                dp[i+1][j+a]=(dp[i+1][j+a]+dp[i][j])%mod
                
    ans=0
    for i in range(N+1):
        ans=(ans+dp[i][-1])%mod
        
    print(ans)
                
            
    
            
        

main()

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

if __name__ == "__main__":
    main()

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

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)]
###dp[i][j][k]:Aのindex[i-1]まで見て和がjになっているもの
###kの意味は解説の通り


dp0[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp0[i+1][j] += dp0[i][j]
        dp0[i+1][j] %= mod

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

        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        dp2[i+1][j] %= mod

        if j+A[i] <= S:
            dp1[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp1[i+1][j+A[i]] %= mod
        
            dp2[i+1][j+A[i]] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+A[i]] %= mod

print(dp2[N][S])

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)]
# dp[0][0] = 1
# for i in range(n):  # ここをrange(i, n)にすると、f(i, r)の計算ができる
#     for j in range(s + 1):
#         dp[i + 1][j] += dp[i][j]  # do NOT use a[i]
#         if j + a[i] <= s:
#             dp[i + 1][j + a[i]] += dp[i][j]  # USE a[i]
# # f(1, n) = dp[n][s]
# # f(1, i) = dp[i][s] (i = 1, 2, ..., n)
# print('dp')
# print(*dp, sep='\n')

dp0 = [[0] * (s + 1) for _ in range(n + 1)]
dp1 = [[0] * (s + 1) for _ in range(n + 1)]
dp0[0][0] = 1
ans = 0
for i in range(n):
    for j in range(s + 1):
        # i番目の要素は使わない
        dp0[i + 1][j] += dp0[i][j]
        dp0[i + 1][j] %= MOD
        dp1[i + 1][j] += dp0[i][j] + dp1[i][j]
        dp1[i + 1][j] %= MOD

        if j + a[i] <= s:
            dp1[i + 1][j + a[i]] += dp0[i][j] + dp1[i][j]
            dp1[i + 1][j + a[i]] %= MOD

    ans += dp1[i + 1][s]
    ans %= MOD
# dp[r][s][1] = \sum_{i=1}^{r} f(i, r)

# print('dp[][][1]')
# for i in range(n + 1):
#     print([dp[i][j][1] for j in range(s + 1)])

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import copy
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 998244353  # type: int


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


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

    print(dp[S][2])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # 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:


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


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

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

Submission status: Accepted

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

n, s = map(int, input().split())
a = [0]
a += list(map(int, input().split()))
#  dp = [[0] * (3010)] * (n + 2)  #
dp = [[0]*(3010) for i in range(n+2)]

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

Submission status: Accepted

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
def main():
    MOD = 998244353
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [0] * (S + 1)
    ans = 0
    for i in range(N):
        dp[0] += 1
        dp2 = [0] * (S + 1)
        for j in range(S+1):
            dp2[j] += dp[j]
            if j + A[i] <= S:
                dp2[j + A[i]] += dp[j] 
                dp2[j + A[i]] %= MOD

        dp = dp2

        ans += dp[S]
        ans %= MOD

    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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


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


print(dp[n][s])

Submission status: Accepted

Solution code:

MOD = 998244353


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


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

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

main()