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: Wrong Answer

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

Submission status: Wrong Answer

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

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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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)]
    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] += 1
        dp[num][right] = 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
from numpy.fft import rfft,irfft
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))

INF=10**20
class Polynomial:
    def __init__(self,coefficient=None,dim=0,const=1):
        if coefficient == None:
            self.coefficient = np.zeros(dim+1, np.int64)
            self.coefficient[dim] = const
        else:
            self.coefficient = coefficient

    def __add__(self,other): # +
        f,g = self.coefficient, other.coefficient
        if len(f) > len(g): f,g = g,f

        h = Polynomial(dim=len(g)-1,const=0)
        h.coefficient[len(f):] += g[len(f):]
        h.coefficient[:len(f)] += f + g[:len(f)]
        return h
    
    def __iadd__(self,other): # +=
        h = self.__add__(other)
        self.coefficient = h.coefficient
        return self

    def __mul__(self,other): # *
        f = self.coefficient
        g = other.coefficient
        h = Polynomial()
        h.coefficient = self.fft(f,g)[:len(f)+len(g)-1]
        return h
    
    def __len__(self):
        return len(self.coefficient)

    def __getitem__(self,key):
        return self.coefficient[key]

    def get_coefficient(self,x):
        return self.coefficient[x]

    def mul_with_mod(self,other,MOD):
        f = self.coefficient
        g = other.coefficient
        h = Polynomial()
        h.coefficient = self.fft_with_mod(f,g,MOD)[:len(f)+len(g)-1]
        return h


    def fft(self,A,B,fft_len=1<<18):
        x = irfft(rfft(A,fft_len) * rfft(B,fft_len))
        return np.rint(x).astype(np.int64)

    def convolve(self,f,g):
        h = self.fft(f,g)[:len(f)+len(g)-1]
        return h

    def fft_with_mod(self,f,g,MOD,fft_len=1<<18):
        f1,f2 = np.divmod(f,1<<15)
        g1,g2 = np.divmod(g,1<<15)

        a = self.convolve(f1,g1) % MOD
        c = self.convolve(f2,g2) % MOD
        b = self.convolve(f1+f2,g1+g2)-(a+c)
        b %= MOD

        h = (a<<30)+(b<<15)+c
        return h % MOD



def main():
    N,S=mi()
    A=list(mi())
    MOD=998244353
 

    ans = 0
    F = Polynomial(const=0)
    for i in range(N):
        f = Polynomial(dim=A[i]) + Polynomial(const=1)
        F += Polynomial(const=1)

        F = F * f
        if S < len(F):
            F.coefficient[S] %= MOD
            ans += F[S] % MOD
    
    print(ans % MOD)
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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:
            g = np.zeros(self.size, np.int64)
            g[dim] = const
            self.f += g
            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)
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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:
            g = np.zeros(self.size, np.int64)
            g[dim] = const
            self.f += g
            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.multiple(f,MOD)
        F.add(f,MOD)
        ans += F.get_coefficient(S)
    
    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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):
    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, 0] += 1
        ans += dp[i, S]
    print(ans)

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: Wrong Answer

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
sys.setrecursionlimit(10**6)
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache(maxsize=None)
def count(i, s, forced=True):
    global n, a
    if s == 0:
        return i + 1
    elif i == 0:
        return 0
    else:
        return (count(i - 1, s) if not forced else 0) + (count(i - 1, s - a[i], False) if a[i] <= s else 0)

print(sum(count(i, s) * (n - i + 1) % M for i in range(1, n + 1)) % M)

Submission status: Wrong Answer

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

def update(newval, length_elems):
  # sequences made up of only the new value
  if newval<= s:
    new_state[newval][0] = length_elems
    new_state[newval][1] = length_elems
  # appending to existing sequences
  for j in range(1, s+1):
    new_state[j][0] += old_state[j][0]
    new_state[j][1] += old_state[j][0] + old_state[j][1]
    if newval+j <= s:
      new_state[newval+j][0] += old_state[j][0]
      new_state[newval+j][1] += old_state[j][0]

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 998244353
N, S = map(int, readline().split())
A = list(map(int,readline().split()))
U = 3010
f = np.zeros(U,np.int64)
ans = 0
for a in A:
    f[0] += 1
    f[a:] += f[:-a].copy()
    ans += f[S]
    ans %= MOD
print(ans)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

N,S=map(int,input().split())
A=list(map(int,input().split()))
dp=[[0 for i in range(S+1)] for j in range(N+1)]
for i in range(1,N+1):
  for s in range(1,S+1):
    if A[i-1] < s:
      dp[i][s]=dp[i-1][s-A[i-1]] + dp[i-1][s]
    elif A[i-1]==s:
      dp[i][s]=1
    else:
      dp[i][s]=dp[i-1][s]
print(np.array(dp).sum())

Submission status: Wrong Answer

Solution code:

N,S = map(int,input().split())
A = list(map(int,input().split()))
#%%
b = [[0]*(S+1) for _ in range(N+1)]
b[0][0] = 0
for r in range(N):
    for s in range(S+1):
        b[r+1][s] += b[r][s]
        if s-A[r]>=0:
            b[r+1][s] += b[r][s-A[r]]
        if s==A[r] or s==0:
            b[r+1][s] += 1

ans = 0
for i in range(N):  
    ans += b[i+1][S]
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    import numpy as np
    dp = np.zeros(s+1, dtype=int)
    dp[0] = 1
    mod = 998244353
    ans = 0
    for i in range(n):
        dp[0] += 1
        dp[a[i]:] += dp[:-a[i]]
        dp%= mod
        ans += dp[-1]
        ans %= mod
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, s = map(int, readline().split())
    a = list(map(int, readline().split()))
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 998244353
N, S = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
coef = np.zeros(3001, dtype=int)
ans = 0
for a in A:
    coef[0] += 1
    coef[a:] += coef[:-a]
    ans += coef[S]
    ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
mod = 998244353
A = list(map(int, input().split()))
L = [0 for _ in range(S+1)]
p = 0
F = {0}
for i in range(N):
    L[0] += 1
    X = [[j, L[j]] for j in F]
    for j in X:
        if j[0] + A[i] <= S:
            L[j[0]+A[i]] += j[1]
            L[j[0]+A[i]] %= mod
            F.add(j[0]+A[i])
    p += L[S]

print(p)

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
*A, = map(int, input().split())

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

dp[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j+A[i]][1] += dp[i][j][0] * (i+1)
        dp[i+1][j+A[i]][2] += dp[i][j][0] * (i+1) * (N-i)

        dp[i+1][j][1] += dp[i][j][1]
        dp[i+1][j+A[i]][1] += dp[i][j][1]
        dp[i+1][j+A[i]][2] += dp[i][j][1] * (N-i)

        dp[i+1][j][2] += dp[i][j][2]

print(dp[N][S][2])

Submission status: Wrong Answer

Solution code:
P = 998244353

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

dp0 = [[0]*(S+1) for _ in range(N)]
dp1 = [[0]*(S+1) for _ in range(N)]
dp2 = [[0]*(S+1) for _ in range(N)]

dp0[0][0] = 1
dp1[0][0] = 1
if A[0] <= S:
    dp1[0][A[0]] = 1

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

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

Submission status: Wrong Answer

Solution code:
P = 998244353

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

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

dp[0][0][0] = 1
dp[0][0][1] = 1
if A[0] <= S:
    dp[0][A[0]][1] = 1

for i in range(1, N):
    for j in range(S+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j][1] += dp[i-1][j][1] + dp[i-1][j][0]
        dp[i][j][2] += dp[i-1][j][2] + dp[i-1][j][1]
        if j + A[i] < S:
            dp[i][j+A[i]][1] += dp[i-1][j][1] + dp[i-1][j][0]
        elif j + A[i] == S:
            dp[i][S][2] += dp[i-1][j][1] + dp[i-1][j][0]
            dp[i][S][1] += dp[i-1][j][1]
        dp[i][j][0] %= P
        dp[i][j][1] %= P
        dp[i][j][2] %= P

print(dp[N-1][S][2])

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    import numpy as np

    mod = 998244353

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

    # 多項式
    polynomial = np.zeros(S+1, int)
    ans = 0
    for i in A:
        polynomial[0] += 1
        polynomial[i:] += polynomial[:-i].copy()
        polynomial %= mod
        ans += polynomial[S]

    print(ans)
    
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    import numpy as np

    mod = 998244353

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

    # 多項式
    polynomial = np.zeros(S+1, int)
    ans = 0
    for i in A:
        polynomial[0] += 1
        polynomial[i:] += polynomial[:-i].copy()
        polynomial %= mod
        ans += polynomial[S]

main()

Submission status: Wrong Answer

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

#まだ左端を選択していない状態(状態 0)。この時は和が0の時1通りでそれ以外は0。
#左端は選択済みだけど右端は選択していない状態(状態 1)
#右端も選択済みの状態(状態 2)

dp = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
#i個目までで和がjとなる場合の数
ans = 0

for i in range(N):
  for j in range(S+1):
    #from 0
    #if j == 0: #j==0の時以外は基本0なのであってもなくても良い。
    dp[i+1][j][0] += dp[i][j][0]
    if j+A[i] <= S:# and j == 0: #j==0の時以外は基本0なのであってもなくても良い。
      dp[i+1][j+A[i]][1] += dp[i][j][0] * (i+1)
      dp[i+1][j+A[i]][2] += dp[i][j][0] * (i+1) * (N-i)
    #from 1
    dp[i+1][j][1] += dp[i][j][1]
    if j+A[i] <= S:
      dp[i+1][j+A[i]][1] += dp[i][j][1]
      dp[i+1][j+A[i]][2] += dp[i][j][1] * (N-i)
    #from 2
    dp[i+1][j][2] += dp[i][j][2]
#print(dp)
print(dp[N][S][2])

Submission status: Wrong Answer

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

#まだ左端を選択していない状態(状態 0)。この時は和が0の時1通りでそれ以外は0。
#左端は選択済みだけど右端は選択していない状態(状態 1)
#右端も選択済みの状態(状態 2)

dp = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
#i個目までで和がjとなる場合の数
ans = 0

for i in range(N):
  for j in range(S+1):
    #from 0
    if j == 0: #j==0の時以外は基本0なのであってもなくても良い。
      dp[i+1][j][0] += dp[i][j][0]
    if j+A[i] <= S and j == 0: #j==0の時以外は基本0なのであってもなくても良い。
      dp[i+1][j+A[i]][1] += dp[i][j][0] * (i+1)
      dp[i+1][j+A[i]][2] += dp[i][j][0] * (i+1) * (N-i)
    #from 1
    dp[i+1][j][1] += dp[i][j][1]
    if j+A[i] <= S:
      dp[i+1][j+A[i]][1] += dp[i][j][1]
      dp[i+1][j+A[i]][2] += dp[i][j][1] * (N-i)
    #from 2
    dp[i+1][j][2] += dp[i][j][2]
#print(dp)
print(dp[N][S][2])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code
def resolve():
    N,S=pin()
    A=tupin()#調子にのるな
    mod=998244353

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

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

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

    F=defaultdict(int)
    G=defaultdict(int)
    F[0]=1 #init
    #F1-F0=f1*(1+G0)=f1+1
    #print(ans)
    for a in A:
        #G
        if len(G)==0:
            G[0]=1
            if a<=S:
                G[a]=1
        else:
            G[0]+=1
            temp=defaultdict(int)
            for g in G:
                temp[g]+=G[g]
                if g+a<=S:
                    temp[g+a]+=G[g]
            G=temp
            
        #Fの計算
        for g in G:
            F[g]+=G[g]
        #print(F)
    print(F[S])



#%%submit!
resolve()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

#係数を記録するための配列
f = np.zeros(s+1)

for i in a:
    f[0] += 1
    f[i:] += f[:-i].copy()
    f %= mod
    ans += f[s]

print(ans)

Submission status: Wrong Answer

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

dp=[[0]*(S+10) for i in range(N+1)]
for i in range(N):
    for j in range(S+1):
        dp[i+1][j]=dp[i][j]
        dp[i+1][j]+=dp[i][j-A[i]] if j>=A[i] else 0
        dp[i+1][j]+=1 if (j==A[i] or j==0) else 0
        dp[i+1][j]%=MOD
print(*dp,sep='\n')
ans=0
for i in range(1,N+1):
    ans=(ans+dp[i][S])%MOD
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
mod= 998244353
@lru_cache(None)
def F(k):#ｆ１＋ｆ２＋．。。ｆｋ
  if k==1:
    res=[0]*(s+1)
    res[0]=1
    if a[0]<s+1:
      res[a[0]]=1
    return res
  res=F(k-1)
  #print(res)
  k-=1
  for i in range(s,-1,-1):
    if i-a[k]>=0:
      res[i]+=res[i-a[k]]
      if res[i]>=mod:
        res[i]-=mod
  if a[k]<s+1:
      res[a[k]]+=1
      if res[i]>=mod:
        res[i]-=mod
  res[0]+=1
  return res
ans=0
for i in range(1,n+1):
  ls=F(i)
  ans+=ls[-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
mod= 998244353
@lru_cache(None)
def F(k):#ｆ１＋ｆ２＋．。。ｆｋ
  if k==1:
    res=[0]*(s+1)
    res[0]=1
    if a[0]<s+1:
      res[a[0]]=1
    return res
  res=F(k-1)
  #print(res)
  k-=1
  for i in range(s,-1,-1):
    if i-a[k]>=0:
      res[i]+=res[i-a[k]]
  if a[k]<s+1:
      res[a[k]]+=1
  res[0]+=1
  return res
ans=0
for i in range(1,n+1):
  ls=F(i)
  ans+=ls[-1]
print(ans)

Submission status: Wrong Answer

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

    MOD = 998244353

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

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

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

U = 3010
count = 0
F = np.zeros(U + 1, np.int64)
for a in A:
    F[0] += 1
    # python 3.4 ではだめみたい
    # FF = F
    # FF[a:] += FF[:-a]
    # FF %= MOD
    # F = FF
    F[a:] += F[:-a].copy()
    F %= MOD # forgot
    count += F[s]
    print(F[0:10])

count %= MOD
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

U = 3010
count = 0
F = np.zeros(U + 1, np.int64)
for a in A:
    F[0] += 1
    # python 3.4 ではだめみたい
    # FF = F
    # FF[a:] += FF[:-a]
    # FF %= MOD
    # F = FF
    F[a:] += F[:-a].copy()
    count += F[s]

count %= MOD
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

count %= MOD
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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]
    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: Wrong Answer

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]
    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(i, w)
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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):
        print(dp)
        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()