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 numpy as np
from sys import stdin

'''
Reference: https://codeforces.com/blog/entry/75046#comment-591494 (1-based index)

(0-based index)

For a sequence A[l]..A[k]..A[r] with sum S contributes l * (N - r) to answer.
    0, 1, 2, ..., l....k....r, ..., N - 2, N - 1
    x  x  x   x   x         v   v     v      v
There are (l + 1) `x` and (N - r) `v`.

Enumerate all possible sequence is impossible. 
Consider all sequeuces with sum S and **ends** at specific r:
    A[l1]...A[r] -> l1 * (N - r)
    A[l2]...A[r] -> l2 * (N - r)
    A[l3]...A[r] -> l3 * (N - r)
    .
    .
    .
which contributes (l1 + l2 + ... + lm) * (N - r) in total.

We can find *sum of left index for all valid sequence* for each r using DP.

    dp[i][s] = the sum of left index for all sequence that
                    1. ends at i
                    2. has sum s
    
    dp[i][:A[i]] = 0  since any sequence ends at i has sum >= A[i]

    dp[i][A[i]] = i + 1
    dp[i][s] = sum(dp[j][s - A[i]] for j in range(i))

    Take A = [2, 3, 4] for example, sequences that end at A[2] are:
    
            Base case:
                   [4] -> dp[2][4] = 3

            Transition from dp[0][s - 4]:
             [2,    4]

            Transition from dp[1][s - 4]:
                [3, 4]
             [2, 3, 4]
    
    The answer is sum(dp[r][S] * (N - r) for r in range(N))

So the naive implementation is:

    dp = np.zeros((N, max(S, A.max()) + 1), dtype=np.int64)
    for i, a in enumerate(A):
        dp[i, a] = i + 1
        for s in range(a + 1, S + 1):
            dp[i, s] = dp[:i, s - a].sum() % M  # here can be optimized
    
    ans = 0
    for i in range(N):
        ans += (N - i) * dp[i, S]
        ans = ans % M

has time O(N * S * N) which results in TLE.

Using another array to store the cumsum (prefix sum) of dp solves the problem.
One can compress the dp matrix to vector to reduce memory usage.
'''

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353
V = max(A.max(), S)

ans = 0
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp = np.zeros(V + 1, dtype=np.int64)
    dp[a] = i + 1
    dp[a + 1 : S + 1] = cs[np.arange(a + 1, S + 1) - a]
    cs = (cs + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin

'''
Reference: https://codeforces.com/blog/entry/75046#comment-591494 (1-based index)

(0-based index)

For a sequence A[l]..A[k]..A[r] with sum S contributes l * (N - r) to answer.
    0, 1, 2, ..., l....k....r, ..., N - 2, N - 1
    x  x  x   x   x         v   v     v      v
There are (l + 1) `x` and (N - r) `v`.

Enumerate all possible sequence is impossible. 
Consider all sequeuces with sum S and **ends** at specific r:
    A[l1]...A[r] -> l1 * (N - r)
    A[l2]...A[r] -> l2 * (N - r)
    A[l3]...A[r] -> l3 * (N - r)
    .
    .
    .
which contributes (l1 + l2 + ... + lm) * (N - r) in total.

We can find *sum of left index for all valid sequence* for each r using DP.

    dp[i][s] = the sum of left index for all sequence that
                    1. ends at i
                    2. has sum s
    
    dp[i][:A[i]] = 0  since any sequence ends at i has sum >= A[i]

    dp[i][A[i]] = i + 1
    dp[i][s] = sum(dp[j][s - A[i]] for j in range(i))

    Take A = [2, 3, 4] for example, sequences that end at A[2] are:
    
                   [4] -> dp[2][4] = 3
             [2,    4] ↘
                [3, 4] -> dp[2][s] = dp[2][s - 4] for all s
             [2, 3, 4] ↗
    
    The answer is sum(dp[r][S] * (N - r) for r in range(N))

So the naive implementation is:

    dp = np.zeros((N, max(S, A.max()) + 1), dtype=np.int64)
    for i, a in enumerate(A):
        dp[i, a] = i + 1
        for s in range(a + 1, S + 1):
            dp[i, s] = dp[:i, s - a].sum() % M  # here can be optimized
    
    ans = 0
    for i in range(N):
        ans += (N - i) * dp[i, S]
        ans = ans % M

has time O(N * S * N) which results in TLE.

Using another array to store the cumsum (prefix sum) of dp solves the problem.
One can compress the dp matrix to vector to reduce memory usage.
'''

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353
V = max(A.max(), S)

ans = 0
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp = np.zeros(V + 1, dtype=np.int64)
    dp[a] = i + 1
    dp[a + 1 : S + 1] = cs[np.arange(a + 1, S + 1) - a]
    cs = (cs + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin

'''
Reference: https://codeforces.com/blog/entry/75046#comment-591494 (1-based index)

(0-based index)

For a sequence A[l]..A[k]..A[r] with sum S contributes l * (N - r) to answer.
    0, 1, 2, ..., l....k....r, ..., N - 2, N - 1
    x  x  x   x   x         v   v     v      v
There are l `x` and (N - r) `v`.

Enumerate all possible sequence is impossible. 
Consider all sequeuces with sum S and **ends** at specific r:
    A[l1]...A[r] -> l1 * (N - r)
    A[l2]...A[r] -> l2 * (N - r)
    A[l3]...A[r] -> l3 * (N - r)
    .
    .
    .
which contributes (l1 + l2 + ... + lm) * (N - r) in total.

We can find *sum of left index for all valid sequence* for each r using DP.

    dp[i][s] = the sum of left index for all sequence that
                    1. ends at i
                    2. has sum s
    
    dp[i][:A[i]] = 0  since any sequence ends at i has sum >= A[i]

    dp[i][A[i]] = i + 1
    dp[i][s] = sum(dp[j][s - A[i]] for j in range(i))

    Take A = [2, 3, 4] for example, sequences that end at A[2] are:
    
                   [4] -> dp[2][4] = 3
             [2,    4] ↘
                [3, 4] -> dp[2][s] = dp[2][s - 4] for all s
             [2, 3, 4] ↗
    
    The answer is sum(dp[r][S] * (N - r) for r in range(N))

So the naive implementation is:

    dp = np.zeros((N, max(S, A.max()) + 1), dtype=np.int64)
    for i, a in enumerate(A):
        dp[i, a] = i + 1
        for s in range(a + 1, S + 1):
            dp[i, s] = dp[:i, s - a].sum() % M  # here can be optimized
    
    ans = 0
    for i in range(N):
        ans += (N - i) * dp[i, S]
        ans = ans % M

has time O(N * S * N) which results in TLE.

Using another array to store the cumsum (prefix sum) of dp solves the problem:
'''

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353
V = max(A.max(), S)

ans = 0
dp = np.zeros((N, V + 1), dtype=np.int64)
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp[i, a] = i + 1
    dp[i, a + 1 : S + 1] = cs[np.arange(a + 1, S + 1) - a]
    cs = (cs + dp[i]) % M
    ans = (ans + (N - i) * dp[i, S]) % M
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin

'''
Reference: https://codeforces.com/blog/entry/75046#comment-591494 (1-based index)

(0-based index)

For a sequence A[l]..A[k]..A[r] with sum S contributes l * (N - r) to answer.
    0, 1, 2, ..., l....k....r, ..., N - 2, N - 1
    x  x  x   x   x         v   v     v      v
There are l `x` and (N - r) `v`.

Enumerate all possible sequence is impossible. 
Consider all sequeuces with sum S and **ends** at specific r:
    A[l1]...A[r] -> l1 * (N - r)
    A[l2]...A[r] -> l2 * (N - r)
    A[l3]...A[r] -> l3 * (N - r)
    .
    .
    .
which contributes (l1 + l2 + ... + lm) * (N - r) in total.

We can find *sum of left index for all valid sequence* for each r using DP.

    dp[i][s] = the sum of left index for all sequence that
                    1. ends at i
                    2. has sum s
    
    dp[i][:A[i]] = 0  since any sequence ends at i has sum >= A[i]

    dp[i][A[i]] = i + 1
    dp[i][s] = sum(dp[j][s - A[i]] for j in range(i))

    Take A = [2, 3, 4] for example, sequences that end at A[2] are:
    
                   [4] -> dp[2][4] = 3
             [2,    4] ↘
                [3, 4] -> dp[2][s] = dp[2][s - 4] for all s
             [2, 3, 4] ↗
    
    The answer is dp[r][S] * (N - r) for r in range(N)

So the naive implementation is:

    dp = np.zeros((N, max(S, A.max()) + 1), dtype=np.int64)
    for i, a in enumerate(A):
        dp[i, a] = i + 1
        for s in range(a + 1, S + 1):
            dp[i, s] = dp[:i, s - a].sum() % M  # here can be optimized
    
    ans = 0
    for i in range(N):
        ans += (N - i) * dp[i, S]
        ans = ans % M

has time O(N * S * N) which results in TLE.

Using another array to store the cumsum (prefix sum) of dp solves the problem:
'''

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353
V = max(A.max(), S)

ans = 0
dp = np.zeros((N, V + 1), dtype=np.int64)
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp[i, a] = i + 1
    dp[i, a + 1 : S + 1] = cs[np.arange(a + 1, S + 1) - a]
    cs = (cs + dp[i]) % M
    ans = (ans + (N - i) * dp[i, S]) % M
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin

'''
Reference: https://codeforces.com/blog/entry/75046#comment-591494 (1-based index)

(0-based index)

For a sequence A[l]..A[k]..A[r] with sum S contributes l * (N - r) to answer.
    0, 1, 2, ..., l....k....r, ..., N - 2, N - 1
    x  x  x   x   x         v   v     v      v
There are l `x` and (N - r) `v`.

Enumerate all possible sequence is impossible. 
Let's consider all sequeuces with sum S and **ends** at r:
    A[l1]...A[r] -> l1 * (N - r)
    A[l2]...A[r] -> l2 * (N - r)
    A[l3]...A[r] -> l3 * (N - r)
    .
    .
    .
which contributes (l1 + l2 + ... + lm) * (N - r) in total.

We can find *sum of left index for all valid sequence* for each r using DP.

    dp[i][s] = the sum of left index for all sequence that
                    1. ends at i
                    2. has sum s
    
    dp[i][:A[i]] = 0  since any sequence ends at i has sum >= A[i]

    dp[i][A[i]] = i + 1
    dp[i][s] = sum(dp[j][s - A[i]] for j in range(i))

    Take A = [2, 3, 4] for example, sequences that end at A[2] are:
    
             [      4] -> dp[2][4] = 3
             [2,    4] ↘
             [   3, 4] -> dp[2][s] = dp[2][s - 4] for all s
             [2, 3, 4] ↗
    
    The answer is dp[r][S] * (N - r) for r in range(N)

So the naive implementation is:

    dp = np.zeros((N, max(S, A.max()) + 1), dtype=np.int64)
    for i, a in enumerate(A):
        dp[i, a] = i + 1
        for s in range(a + 1, S + 1):
            dp[i, s] = dp[:i, s - a].sum() % M  # can be optimized
    
    ans = 0
    for i in range(N):
        ans += (N - i) * dp[i, S]
        ans = ans % M

has time O(N * S * N) which results in TLE.

Using another array to store the cumsum (prefix sum) of dp solves the problem:
'''

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353
V = max(A.max(), S)

ans = 0
dp = np.zeros((N, V + 1), dtype=np.int64)
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp[i, a] = i + 1
    dp[i, a + 1 : S + 1] = cs[np.arange(a + 1, S + 1) - a]
    cs = (cs + dp[i]) % M
    ans = (ans + (N - i) * dp[i, S]) % M
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


mo=998244353

ans=0
n,s=LI()
a=LI()

def dyn(n,A,a):
    dp=[[0]*(A+1) for i in range(n+1)]
    for i in range(n):
        x=a[i]
        dp[i+1]=dp[i][:]
        dp[i+1][x]+=1+i
        for j in range(x,A+1):
            dp[i+1][j]+=dp[i][j-x]
            dp[i+1][j]%=mo
    return dp

dp=dyn(n,3000,a)

for i in dp:
    ans+=i[s]
    ans%=mo

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True


mo=998244353

ans=0

n,s=LI()
a=LI()

A=3000



def dyn(n,A,a):
    dp=[[0]*(A+1) for i in range(n+1)]
    
    for i in range(n):
        x=a[i]
        dp[i+1]=dp[i][:]
        dp[i+1][x]+=1+i
        for j in range(x,A+1):
            #show(i,j,x)
            dp[i+1][j]+=dp[i][j-x]
            dp[i+1][j]%=mo
    return dp

dp=dyn(n,A,a)

ans=0
for i in dp:
    ans+=i[s]
    ans%=mo
    #show(i)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353
V = max(max(A), S)

ans = 0
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp = np.zeros(V + 1, dtype=np.int64)
    dp[a] = i + 1
    dp[a + 1 : S + 1] = cs[np.arange(a + 1, S + 1) - a]
    cs = (cs + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp = np.zeros(V + 1, dtype=np.int64)
    dp[a] = i + 1
    dp[a + 1 : S + 1] = cs[np.arange(a + 1, S + 1) - a]
    cs = (cs + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int,stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = [0 for _ in range(V + 1)]
for i, a in enumerate(A):
    dp = [0 for _ in range(V + 1)]
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cs[s - a]
    cs = [(a + b) % M for a, b in zip(cs, dp)]
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Accepted

Solution code:
N,S=map(int,input().split())
A=list(map(int,input().split()))
m=998244353
import numpy as np
dp=np.zeros((N+1,S+1),dtype=np.int64)
dp[:,0]=[1]*(N+1)
for i,a in enumerate(A):
    dp[i+1]+=dp[i]
    dp[i+1,a:]=(dp[i+1,a:]+dp[i,:-a])%m
print(np.sum(dp[:,-1])%m)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
# MOD = 10 ** 9 + 7
MOD = 998244353

# 解説
N, S = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

# dp[i][k]: iまで見て、合計がkの場合の数
dp = [[0] * S for _ in range(N + 1)]
ans = 0
for i in range(N):
    for k in range(S):
        dp[i + 1][k] += dp[i][k]
        dp[i + 1][k] %= MOD
        if k == 0 and k + A[i] < S:
            # ここから使う
            # L の選び方が i + 1 ある
            dp[i + 1][A[i]] += i + 1
            dp[i + 1][A[i]] %= MOD
        elif k == 0 and k + A[i] == S:
            ans += (i + 1) * (N - i)
        elif k + A[i] < S:
            dp[i + 1][k + A[i]] += dp[i][k]
            dp[i + 1][k + A[i]] %= MOD
        elif k + A[i] == S:
            # ここまで使う
            # R の選び方が N - i ある
            ans += dp[i][k] * (N - i)
        ans %= MOD
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j] := i番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j] := i番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j] := i番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は普通
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp1[i][j]
        dp2[i+1][j] += dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            # 左端を決める時はそこより手前が自由に使えるのでその分を掛ける
            dp1[i+1][j+a] += dp0[i][j] * (i+1)
            # 右端を決める時はそこより先が自由に使えるのでその分を掛ける
            dp2[i+1][j+a] += dp1[i][j] * (N-i)
            dp1[i+1][j+a] += dp1[i][j] 
            dp2[i+1][j+a] += dp0[i][j] * (i+1) * (N-i)
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)

Submission status: Accepted

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 998244353

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


dp = [np.zeros(S + 10, dtype=np.int64) for _ in range(N+1)]
#dp[0][0] = 1

# print(dp[0])
ans = 0
for i in range(N):
    a = A[i]

    dp[i][0] += 1
    dp[i + 1] += dp[i]
    dp[i + 1] %= MOD

    # a足す
    dp[i + 1][a:] += dp[i][:-a]
    dp[i + 1] %= MOD

    #print(dp[i + 1])
    ans += dp[i + 1][S]
    ans %= MOD

print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

dp0 = [0] * (S+1)
dp1 = [0] * (S+1)
dp2 = [0] * (S+1)
nxt0 = [0] * (S+1)
nxt1 = [0] * (S+1)
nxt2 = [0] * (S+1)
dp0[0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        nxt0[j] += dp0[j]
        nxt1[j] += dp0[j] + dp1[j]
        nxt2[j] += dp0[j] + dp1[j] + dp2[j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            nxt1[j+a] += dp0[j] + dp1[j]
            nxt2[j+a] += dp0[j] + dp1[j]
        nxt0[j] %= MOD
        nxt1[j] %= MOD
        nxt2[j] %= MOD
    dp0 = nxt0[:]
    dp1 = nxt1[:]
    dp2 = nxt2[:]
    nxt0 = [0] * (S+1)
    nxt1 = [0] * (S+1)
    nxt2 = [0] * (S+1)
ans = dp2[S]
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j] := i番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j] := i番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j] := i番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j] := j番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j] := j番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j] := j番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j][ := j番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j][ := j番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j][ := j番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
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

res = 0
dp = np.zeros(s + 1, dtype = int)

for i in range(n):
    dp[0] += 1
    dp[a[i]:] += dp[:-a[i]].copy()
    dp %= mod
    res += dp[s]
    res %= mod

print(res)

Submission status: Accepted

Solution code:
import numpy as np

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

ans = 0
dp = np.zeros(S + 1, dtype=np.int64)

for a in A:
    dp[0] += 1
    dp[a:] += dp[: -a].copy()
    dp %= MOD
    ans += dp[S]

print(ans % MOD)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 998244353
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

#参考:https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2019-03-22abc-159

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

Submission status: Accepted

Solution code:
from sys import stdin
mod = 998244353
def solveAsPolynomial():
    import numpy as np
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().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[0] += 1#f+1
        f[A:] += f[:-A].copy()#f*(1+x**A)
        f %= mod
        ans += f[S]
        #x**S = X**(A_1+...+A_k)ゆえ、f[S]は知りたい組み合わせの数と等しい
        ans %= mod
    return ans
def main():
  ans = solveAsPolynomial()
  print(ans)
if __name__ =="__main__":
  main()

Submission status: Accepted

Solution code:
from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [0]*(S+1)
    ans = 0
    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[S]
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [0]*(S+1)
    ans = 0
    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[S]
        ans %= mod
    print(ans)
if __name__ == "__main__":
    main()