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: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
B=[[[] for i in range(s+1)] for _ in range(n+1)]
B[0][0].append(0)
ans=0
for i in range(n):
  a=A[i]
  if a<=s:
    B[i+1][a]+=[i+1]
  for j in range(s+1):
    B[i+1][j]+=B[i][j]
    if j-a>=0 and B[i][j-a]:
      B[i+1][j]+=B[i][j-a]
    
  for aa in B[i+1][s]:
    ans+=aa
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
inpl = lambda: list(map(int,input().split()))
N, S = inpl()
A = inpl()
ans = 0
comb = set()
pool = [(0,None,0)] # node, start, sum
while pool:
    i, start, s = pool.pop()
    if i < N-1:
        pool.append((i+1,start,s))
    s += A[i]
    if start is None:
        start = i
    if s == S:
        ans += (start+1) * (N-i)
        ans %= MOD
    elif s < S and i < N-1:
        pool.append((i+1,start,s))
print(ans)

Submission status: Time Limit Exceeded

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

def dypr(nums, S):
    N = len(nums)
    dp = [[0 for i in range(S + 1)] for j in range(N + 1)]
    dp[0][0] = 1

    for i in range(N):
        for j in range(S + 1):
            if nums[i] <= j:
                dp[i + 1][j] = dp[i][j - nums[i]] + dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]
#    print(dp)
#    print(dp[N])
#    print(dp[N][S])
    return dp[N][S]

total = 0
for i in range(N):
#    print("===")
    for j in range(i, N):
        total += dypr(nums[i: j + 1], S)
        #print(total)
print(total % 998244353)

Submission status: Time Limit Exceeded

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

dp  = {0:(0,0)}

for i in range(n):
  a = A[i]
  eph = {}
  for j in dp:
    if j==0:
      eph[a] = [(i+1,i+1)]
      continue
    if j+a > s:
      continue
    eph[j+a] = [(k[0],i+1) for k in dp[j]] 
  for e in eph:
    if e in dp:
      dp[e].extend(eph[e])
    else:
      dp[e] = eph[e]
 

if s in dp:
  cand = dp[s]
else:
  print(0)
  exit()
cand.sort(key = lambda x:(x[0],x[1]))


ans = 0
index = 0
for l,r in cand:
  ans += ((l)*(n-r+1)) % MOD
  ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:

n, s = (int(x) for x in input().split())
arr = [int(x) for x in input().split()]

MOD = 998244353

def knabsack(arr):
    n = len(arr)
    smax = sum(arr)
    if s > smax:
        return 0
    dp = [[0 for _ in range(smax+1)] for _ in range(n+1)]
    dp[-1][0] = 1
    sol = 0
    for i in range(n):
        for ss in range(smax+1):
            dp[i][ss] = (dp[i-1][ss] + (dp[i-1][ss-arr[i]] if ss-arr[i] >= 0 else 0)) % MOD
        sol = (sol + dp[i][s]) % MOD
    return sol

sol = 0
for i in range(n):
    sol = (sol + knabsack(arr[i:]))%MOD

print(sol)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

mod = 998244353
N, S = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
dp = [defaultdict(int) for j in range(S+1)]
for i in range(1, N+1):
    a = A[i-1]
    for j in range(a+1, S+1)[::-1]:
        for k, v in dp[j-a].items():
            dp[j][k] += v
    if a <= S:
        dp[a][i] = 1
    for k, v in dp[S].items():
        ans += (k * (N-i+1)) * v % mod
        ans %= mod
        dp[S] = defaultdict(int)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

n, s = map(int, input().split())
a = list(map(int, input().split()))
selections = []
for i in range(1, n + 1):
    for selection in combinations(range(n), i):
        if sum([a[j] for j in selection]) == s:
            selections.append(list(selection))

ans = 0
for selection in selections:
    ans += (selection[0] + 1) * (n - selection[-1])
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache

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

@lru_cache(maxsize=None)
def calc(i, j):
    dp = defaultdict(int)
    dp[0] = 1
    for a in A[i:j]:
        newDp = defaultdict(int)
        for s, c in dp.items():
            newDp[s] += c
            newDp[s + a] += c
        dp = newDp
    return dp[S]

ans = 0
MOD = 998244353
for left in range(N):
    for right in range(left + 1, N + 1):
        ans += calc(left, right)
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

DP = [[defaultdict(int) for x in range(N)] for y in range(N)]

for i in range(N):
    DP[i][i][A[i]] = 1

for i in range(N):
    for j in range(i,N):
        for k,v in DP[i][j].items():
            for h in range(j+1,N):
                s = A[h] + k
                if A[h] + k > S:
                    continue
                DP[i][h][s] += v

s = 0
for i in range(N):
    for j in range(N):
        s += DP[i][j][S] * (i + 1) * (N - j)
        s %= 998244353

print(s)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,S =(int(x) for x in  input().split())
As=[int(x) for x in input().split()]
import itertools 
LRs=list(itertools.combinations_with_replacement(range(N),2))
combinations = itertools.combinations
res=0
for i in LRs:
    if i[1]==N-1:
        LR=As[i[0]:]
    else:
        LR=As[i[0]:i[1]+1]
    for x in range(len(LR)):
        res+=sum(1 for y in list(combinations(LR,x+1)) if sum(y)==S)
print(res%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,s = inpm()
    a = inpl()
    if sum(a)<s or min(a)>s:
        print(0)
        return
    past = deque()
    past.append([0,-1])
    ans = 0
    for i in range(n):
        for _ in range(len(past)):
            [x,y] = past.popleft()
            if y == -1:
                Next = [x+a[i],i]
            else:
                Next = [x+a[i],y]
            if Next[0] == s:
                if y == -1:
                    ans += (i+1)*(n-i)
                else:
                    ans += (y+1)*(n-i)
                ans %= mod
            elif Next[0] < s:
                past.append(Next)
            past.append([x,y])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,S =(int(x) for x in  input().split())
As=[int(x) for x in input().split()]
import itertools 
LRs=list(itertools.combinations_with_replacement(range(N),2))
combinations = itertools.combinations
res=0
for i in LRs:
    if i[1]==N-1:
        if i[0]==0:
            LR=As[:]
        else:
            LR=As[i[0]:]
    else:
        if i[0]==0:
            LR=As[:i[1]+1]
        else:
            LR=As[i[0]:i[1]+1]
    for x in range(len(LR)):
        xs=[1 for y in list(combinations(LR,x+1)) if sum(y)==S]
        res+=len(xs)
print(res%998244353)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, S = map(int, input().split())
As = list(map(int, input().split()))

ans = 0
for i in range(N):
    cts = Counter([0])
    for j in range(i, N):
        a = As[j]
        ncts = Counter()
        for k, v in cts.items():
            ncts[k] += v
            ncts[k+a] += v
        cts = ncts
        ans += cts[S]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, s = map(lambda i: int(i), input().split())
A = list(map(lambda i: int(i), input().split()))

def cals(l, r):
    dp = [0 for i in range(s+1)]
    dp[0] = 1
    nonzeros = set([0])
    for a in A[l:r+1]:
        _nonzeros = set()
        for ind in reversed(sorted(nonzeros)):
            if a + ind > s:
                continue
            dp[ind + a] += dp[ind]
            _nonzeros.add(ind + a)
        nonzeros |= _nonzeros
    return dp[s]

ans = 0
for i in range(n):
    for j in range(i, n):
        ans += cals(i, j)%998244353

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] += i + 1
    ans = (ans + (X[S] - pre) * (N - i)) % P
    pre = X[S]
print(ans % P)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] += i + 1
    ans += (X[S] - pre) * (N - i)
    pre = X[S]
print(ans % P)

Submission status: Time Limit Exceeded

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

dp = [[1 if _2 == 0 else 0 for _2 in range(s + 1)] for _1 in range(n+1)]

MOD = 998244353

for i, ai in enumerate(a):
  for j, v in enumerate(dp[i]):
    dp[i + 1][j] += v
    dp[i + 1][j] %= MOD 
    if j + ai <= s:
      dp[i + 1][j + ai] += v
      dp[i + 1][j + ai] %= MOD


print(sum(dp_i[s] for dp_i in dp) % MOD)

Submission status: Time Limit Exceeded

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

def dypr(nums, S):
    N = len(nums)
    dp = [[0 for i in range(S + 1)] for j in range(N + 1)]
    dp[0][0] = 1

    for i in range(N):
        for j in range(S + 1):
            if nums[i] <= j:
                dp[i + 1][j] = dp[i][j - nums[i]] + dp[i][j]
            else:
                dp[i + 1][j] = dp[i][j]
    return dp[N][S]

total = 0
for i in range(N):
    for j in range(i, N):
        total += dypr(nums[i:j+1], S)
print(total % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,S = inputIL()
l = inputIL()

from functools import lru_cache
@lru_cache(maxsize=None)

def f(mi,ma,s):
  if s == 0:
    return 1
  if mi == ma:
    if s == l[mi]:
      return 1
    else:
      return 0
  if mi + 1 == ma:
    if l[mi]+l[ma]==s:
      return 1
    if l[mi] == s or  l[ma] == s:
      if l[mi] == s and  l[ma] == s:
        return 2
      else:
        return 1
    else:
      return 0
  else:
    return f(mi+1,ma-1,s) + f(mi+1,ma-1,s-l[mi]) + f(mi+1,ma-1,s-l[ma]) + f(mi+1,ma-1,s-l[mi]-l[ma]) % MOD
  

ans = 0
for mi in range(N):
  for ma in range(mi,N):
    ans += f(mi,ma,S)
    
print(ans)

Submission status: Time Limit Exceeded

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

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

B = []
t = 0
import itertools
for i in range(0, n):
    for j in range(i, n):
        # if sum(A[i:j+1]) == s:
            # B.append([i, j])
        for l in range(1, j - i + 1+1):
            for k in itertools.combinations(A[i:j+1], l):
                if sum(k) == s:
                    t += 1

print(t)

Submission status: Time Limit Exceeded

Solution code:
n, s = map(lambda i: int(i), input().split())
A = list(map(lambda i: int(i), input().split()))

def cals(l, r):
    dp = [0 for i in range(s+1)]
    dp[0] = 1
    for a in A[l:r+1]:
        for i in reversed(range(len(dp)-a)):
            if dp[i]:
                dp[i+a] += dp[i]
    return dp[s]

ans = 0
for i in range(n):
    for j in range(i, n):
        ans += cals(i, j)%998244353

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353

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

ans = 0

for i, x in enumerate(a):
    if x < s:
        dp[i+1][x] = i + 1
    if x == s:
        ans = (ans + (n-i) * (i+1)) % MOD
    for j in range(1, s):
        if dp[i][j] > 0:
            dp[i+1][j] = (dp[i+1][j] + dp[i][j]) % MOD
            if j + x < s:
                dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j]) % MOD
            elif j + x == s:
                ans = (ans + dp[i][j] * (n-i)) % MOD

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[] for _2 in range(s + 1)] for _1 in range(n)]

for i, ai in enumerate(a):
  if ai <= s:
    dp[i][ai].append((i, i))
  if i > 0:
    for j, t in enumerate(dp[i-1]):
      for r, l in t:
        dp[i][j].append((r, l))
        if j + ai <= s:
          dp[i][j + ai].append((r, i))
        
print(sum((r + 1) * (n - l) for r, l in dp[n-1][s]))

Submission status: Accepted

Solution code:
N,S=map(int,input().split())
dp=[0]*3001
res=0
for i,a in enumerate(map(int,input().split())):
    for w in range(S-a,0,-1):
        dp[w+a]+=dp[w]
    dp[a]+=i+1
    res+=dp[S]
print(res%998244353)

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)

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

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

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

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

    print(dp[s])

main()

Submission status: Accepted

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

dp=[[0]*(S+1) for _ in range(N+1)]
dp[0][0]=0
ans=0
for i in range(N):
    dp[i+1][0]+=1
    if a[i]<=S:
        dp[i+1][a[i]]+=1
    for j in range(S+1):
        dp[i+1][j]+=dp[i][j]

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


print(ans)

Submission status: Accepted

Solution code:
import sys

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

DP = [0 for s in range(S+1)]
ans = 0
for i in range(N):
  a = A[i]
  for s in range(S,-1,-1):
    if s+a <= S:
      DP[s+a] += DP[s]
  if a <= S:
    DP[a] += i+1 #始点がiの列
  ans += DP[S]
  #print(DP, ans)
  
print(ans % MOD)

Submission status: Accepted

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

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

# ある数の取り得る状態は以下
# (1)Lの区間がまだ開始していない
# (2)L-Rの区間に含まれ、和に使われている
# (3)L-Rの区間に含まれ、和に使われていない
# (4)Rの区間が終了している

# dp[i][j][k] = i - 1個目まで処理したときに、区間の開始状況がjで、総和がkになっている個数
dp = [[[0] * (S + 1) for j in range(3)] for i in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
  for k in range(S + 1):
    # (1)まだ区間が開始していない場合
    dp[i + 1][0][k] += dp[i][0][k]
    dp[i + 1][0][k] %= DIV

    # (2)区間に含まれ、和に使われている
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][0][k]
      dp[i + 1][1][k + A[i]] += dp[i][1][k]
      dp[i + 1][1][k + A[i]] %= DIV

    # (3)区間に含まれ、和に使われていない
    dp[i + 1][1][k] += dp[i][0][k]
    dp[i + 1][1][k] += dp[i][1][k]
    dp[i + 1][1][k] %= DIV

    # (4)区間が終了している
    dp[i + 1][2][k] += dp[i][2][k]
    dp[i + 1][2][k] += dp[i][1][k]
    dp[i + 1][2][k] %= DIV

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

Submission status: Accepted

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

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

# ある数の取り得る状態は以下
# (1)Lの区間がまだ開始していない
# (2)L-Rの区間に含まれ、和に使われている
# (3)L-Rの区間に含まれ、和に使われていない
# (4)Rの区間が終了している

# dp[i][j][k] = i - 1個目まで処理したときに、区間の開始状況がjで、総和がkになっている個数
dp = [[[0] * (S + 1) for j in range(3)] for i in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
  for k in range(S + 1):
    # (1)まだ区間が開始していない場合
    dp[i + 1][0][k] += dp[i][0][k]
    dp[i + 1][0][k] %= DIV

    # (2)区間に含まれ、和に使われている(開始していない区間からくる)
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][0][k]
      dp[i + 1][1][k + A[i]] %= DIV

    # (2)区間に含まれ、和に使われている(開始済みの区間からくる)
    if k + A[i] <= S:
      dp[i + 1][1][k + A[i]] += dp[i][1][k]
      dp[i + 1][1][k + A[i]] %= DIV
      
    # (3)区間に含まれ、和に使われていない（開始していない区間からくる）
    dp[i + 1][1][k] += dp[i][0][k]
    dp[i + 1][1][k] %= DIV
    
    # (3)区間に含まれ、和に使われていない（開始済みの区間からくる）
    dp[i + 1][1][k] += dp[i][1][k]
    dp[i + 1][1][k] %= DIV

    # (4)区間が終了している（開始済みの区間からくる）
    dp[i + 1][2][k] += dp[i][1][k]
    dp[i + 1][2][k] %= DIV
    
    # (4)区間が終了している（終了済みの区間からくる）
    dp[i + 1][2][k] += dp[i][2][k]
    dp[i + 1][2][k] %= DIV

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
from collections import defaultdict

MOD = 998244353


def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
#    dp = [defaultdict(int) for _ in range(S)]
    dp = [0] * S
    ans = 0
    for right in range(N):
        num = A[right]
        if num > S:
            continue
        elif num == S:
            ans = (ans + (right+1) * (N-right)) % MOD
            continue
        # for left in dp[S-num]:
        #     cnt = dp[S-num][left]
        #     ans = (ans + (left+1) * (N-right) * cnt) % MOD
        # for i in range(S-num-1, -1, -1):
        #     for left in dp[i]:
        #         dp[i+num][left] += dp[i][left]
        # dp[num][right] = 1
        ans = (ans + dp[S-num] * (N-right)) % MOD
        for i in range(S-num-1, -1, -1):
            dp[i+num] += dp[i]
        dp[num] += right + 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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


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


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] # dim分係数情報をずらす
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        self.f %= MOD
    
    def add(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfに足す
        for dim,const in polynomial:
            self.f[dim] += const
            self.f %= MOD

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



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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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


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


    def multiple(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfにかけ合わせる
        new_F = np.zeros(self.size, np.int64)
        for dim,const in polynomial:
            if dim != 0:
                g = np.zeros(self.size, np.int64)
                g[dim:] += self.f[:-dim] # dim分係数情報をずらす
            else:
                g = const * self.f.copy()

            new_F += g

        self.f = new_F
        self.f %= MOD
    
    def add(self,polynomial,MOD): # const1 * x^dim1 + const2 * x^dim2 + ... をfに足す
        for dim,const in polynomial:
            self.f[dim] += const
            self.f %= MOD

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



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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import numpy as np

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

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

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

Submission status: Accepted

Solution code:
import sys

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

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
_, S = map(int, input().split())
#L = [int(input()) for i in range(N)]
A = tuple(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]
mod=998244353

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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
_, S = map(int, input().split())
#L = [int(input()) for i in range(N)]
#A = tuple(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]
mod=998244353

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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
N, S = map(int, input().split())
#L = [int(input()) for i in range(N)]
A = tuple(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]
mod=998244353

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

print(ans)

Submission status: Accepted

Solution code:
import sys

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

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
N, S = map(int, input().split())
#L = [int(input()) for i in range(N)]
A = tuple(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]
mod=998244353

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

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

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

#N = int(input())
N, S = map(int, input().split())
#L = [int(input()) for i in range(N)]
A = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]
mod=998244353

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

print(ans)