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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    a = LI()
    r = 0
    dp = [0] * (s+1)
    dp[0] = 1
    for i in range(n):
        ai = a[i]
        if ai > s:
            continue
        dp[s] += dp[s-ai] * (n-i)
        dp[s] %= mod2
        for j in range(s-1, ai-1, -1):
            dp[j] += dp[j-ai]
            dp[j] %= mod2
        dp[0] += 1

    return dp[-1]


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    a = LI()
    r = 0
    dp = [0] * (s+1)
    dp[0] = 0
    for i in range(n):
        ai = a[i]
        if ai > s:
            continue
        dp[s] += dp[s-ai] * (n-i)
        dp[s] %= mod2
        for j in range(s-1, ai, -1):
            dp[j] += dp[j-ai]
            dp[j] %= mod2
        dp[ai] += i + 1
        dp[ai] %= mod2

    return dp[-1]


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    a = LI()
    r = 0
    dp = [0] * (s+1)
    dp[0] = 0
    for i in range(n):
        ai = a[i]
        if ai > s:
            continue
        dp[s] += dp[s-ai] * (n-i)
        for j in range(s-1, ai, -1):
            dp[j] += dp[j-ai]
            dp[j] %= mod2
        dp[ai] += i + 1
        dp[ai] %= mod2

    return dp[-1]


print(main())

Submission status: Wrong Answer

Solution code:
N, S=map(int, input().split())
A=list(map(int, input().split()))
tmp=max(A+[S])

dp=[[[0]*3 for s in range(tmp+1)] for i in range(N)]
dp[0][0][0]=1
dp[0][A[0]][1]=1
dp[0][A[0]][2]=1

for i in range(1, N):
    dp[i][0][0]=i+1
    dp[i][A[i]][1]=1
    dp[i][A[i]][2]=1
    for s in range(A[i]):
        dp[i][s][1]=dp[i-1][s][1]
        dp[i][s][2]=dp[i-1][s][2]+dp[i-1][s][1]
        
    for s in range(A[i], S+1):
        dp[i][s][1]=dp[i][s-A[i]][0]+dp[i-1][s-A[i]][1]+dp[i-1][s][1]
        dp[i][s][2]=dp[i-1][s][2]+dp[i][s-A[i]][0]+dp[i-1][s][1]+dp[i-1][s-A[i]][1]
        
print(dp[-1][S][2])

Submission status: Wrong Answer

Solution code:
n, S = map(int, input().split())
a = list(map(int, input().split()))
dp1 = [[0 for _ in range(S+1)] for _ in range(n+1)]
dp2 = [[0 for _ in range(S+1)] for _ in range(n+1)]
for i in range(1, n+1): #Lのみ定めたdp1
	for s in range(S+1):
		if s < a[i-1]:
			dp1[i][s] = dp1[i-1][s]
		elif s == a[i-1]:
			dp1[i][s] = dp1[i-1][s] + i
		else:
			dp1[i][s] = dp1[i-1][s] + dp1[i-1][max(s-a[i-1],0)]

for i in range(1, n+1): #L, Rを定めたdp2
	for s in range(S+1):
		if s < a[i-1]:
			dp2[i][s] = dp2[i-1][s]
		elif s == a[i-1]:
			dp2[i][s] = dp2[i-1][s] + i*(n-i+1)
		else:
			dp2[i][s] = dp2[i-1][s] + dp1[i-1][max(s-a[i-1],0)] * (n-i+1)

print(dp2[n][s])

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))

    dp0 = [[0 for _ in range(S+1)] for _ in range(N+1)]
    dp1 = [[0 for _ in range(S+1)] for _ in range(N+1)]
    dp2 = [[0 for _ in range(S+1)] for _ in range(N+1)]
    dp0[0][0] = 1
    for i in range(N):
        a = A[i]
        dp0i = dp0[i]
        dp1i = dp1[i]
        dp2i = dp2[i]
        dp0n = dp0[i+1]
        dp1n = dp1[i+1]
        dp2n = dp2[i+1]
        for j in range(S+1):
            dp0ij = dp0i[j]
            dp1ij = dp1i[j]

            dp0n[j] = mod_add(dp0n[j], dp0ij)
            dp1n[j] = mod_add(dp1n[j], dp1ij)
            dp2n[j] = mod_add(dp2n[j], dp2i[j])

            if j+a > S: continue
            to1 = dp0ij * (i+1)
            to1 += dp1ij
            dp1n[j+a] = mod_add(dp1n[j+a], to1)
            to1 *= (N-i)
            dp2n[j+a] = mod_add(dp2n[j+a], to1)

    print(dp2[N][S])

MOD = 998244353

def mod_inverse(self):
    a, b = self.value, MOD
    u, v = 1, 0
    while b:
        t = a // b
        b, a = a - t * b, b
        v, u = u - t * v, v
    if u < 0: u += MOD
    return u

def mod_add(self, other):
    self += other
    if self >= MOD: self -= MOD
    return self

def mod_sub(self, other):
    self -= other
    if self < 0: self += MOD
    return self

def mod_mul(self, other):
    self = self * other % MOD
    return self

def mod_div(self, other):
    self *= mod_inverse(other)
    return self

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, s = list(map(int, input().split()))
al = list(map(int, input().split()))
dp = [[0]*3001 for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(3001):
        dp[i+1][j] += dp[i][j]
        if j+al[i] <= 3000:
            dp[i+1][j+al[i]] += dp[i][j]
    dp[i+1][0] += 1
    if j+al[i] <= 3000:
        dp[i+1][al[i]] += 1
ans = 0
for i in range(n):
    ans += dp[i+1][s]
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        if x > S: continue
        dp[0] += 1
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
 
# 状態リストを作成
m = np.zeros((S+1,3))
p = np.zeros((S+1,3))
p[0,0] = 1

# 前状態から次状態の場合数を計算
for i in range(1,N+1):
    
    # x[i] を加えない場合
    m[:,0] = p[:,0]
    m[:,1] = p[:,0] + p[:,1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
    m[:,2] = p[:,0] + p[:,1] + p[:,2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

    # x[i] を加える場合
    m[x[i-1]:,1] += p[:-x[i-1],0] + p[:-x[i-1],1]
    m[x[i-1]:,2] += p[:-x[i-1],0] + p[:-x[i-1],1]

    p[:,0] = m[:,0] % 998244353
    p[:,1] = m[:,1] % 998244353
    p[:,2] = m[:,2] % 998244353
            
print(int(m[S,2]))

Submission status: Wrong Answer

Solution code:
import numpy as np
n,s = map(int, input().split( ))

a = np.array(list(map(int, input().split( ))))

dp = np.array([[0]*3001 for i in range(n)])
dp[0][0] = 1
dp[0][a[0]] = 1

ans = 0

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

Submission status: Wrong Answer

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

*a, = map(int, input().split( ))

dp = [[0]*(3001) for i in range(n)]
dp[0][0] = 1
dp[0][a[0]] = 1

ans = 0

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

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

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

ans = 0
dp = [0]*(S+1)
for i in range(N):
    dp[0] += 1      # Lがiからを足す
    next_dp = [0]*(S+1)
    for j in range(S+1):
        next_dp[j] += dp[j]             # A[i]を選ばない
        next_dp[j] %= MOD
        if j+A[i]<=S:
            next_dp[j+A[i]] += dp[j]    # A[i]を選ぶ
            next_dp[j] %= MOD
    dp = next_dp
    ans += dp[S]    # Rがiまでを足す

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
MOD = 998244353

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]
  dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]

print(dt[N,S] % 998244353)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import numpy as np
N, S = list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

dt = np.array([[0 for _ in range(S+1)] for x in range(N+1)])

for n in range(1, N+1):
  if A[n] <= S:
    dt[n,A[n]] += n
    dt[n,:] += dt[n-1,:] * 2 - dt[n-2,:]
    dt[n, A[n]+1:] += dt[n-1,1:S-A[n]+1] - dt[n-2,1:S-A[n]+1]

print(dt[N,S] % 998244353)

Submission status: Wrong Answer

Solution code:
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)]
sumdp = [0 for i in range(S+1)]

dp[0][0] = 1
sumdp[0] = 1

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

Submission status: Wrong Answer

Solution code:
import numpy as np

def main():
    n, s = map(int, input().split())
    nums = [int(c) for c in input().split()]
    mod = 998244353
    dp = np.zeros(s+1, dtype=int)
    ans = 0

    for i, num in enumerate(nums, 1):
        dp[0] = i
        if num <= s:
            dp[num:] = dp[num:] + dp[:-num]
            # print(dp)
        ans = (ans + dp[-1]) % mod
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np

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

fwd_acc = np.zeros((n + 1, s + 1), dtype=np.int64)
fwd_acc[0][0] = 1

ans = 0
MOD = 998244353
for i, a in enumerate(aaa, start=1):
    fwd_acc[i] = fwd_acc[i - 1]
    fwd_acc[i][0] = i
    if a <= s:
        fwd_acc[i][a:] = fwd_acc[i][a:] + fwd_acc[i][:-a]
    ans = (ans + fwd_acc[i][s]) % MOD
    # print(fwd_acc)
    # print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

fwd_acc = np.zeros((n + 1, s + 1), dtype=np.int64)
fwd_acc[0][0] = 1

ans = 0
MOD = 998244353
for i, a in enumerate(aaa, start=1):
    fwd_acc[i] = fwd_acc[i - 1]
    fwd_acc[i][0] = i
    if a <= s:
        fwd_acc[i][a:] += fwd_acc[i][:-a]
    ans = (ans + fwd_acc[i][s]) % MOD
    # print(fwd_acc)
    # print(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import itertools
A = [0]
N, S = list(map(int, input().split()))
A = A + list(map(int, input().split()))   
print(N,S,A)
val = 0
for L in range(1, N+1):
  for R in range(L, N+1):
    A_ = A[L:R+1]
    lists = []
    for n in range(len(A_)):
      for comb in itertools.combinations(A_, n+1):
        lists.append(list(comb))
    for lis in lists:
      _sum = sum(lis)
      if _sum == S:
        val += 1
      if val == 998244353:
        val = 0
print(val)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import itertools
A = [0]
N, S = list(map(int, input().split()))
A = A + list(map(int, input().split()))   
print(N,S,A)
val = 0
for L in range(1, N+1):
  for R in range(L, N+1):
    A_ = A[L:R+1]
    lists = []
    for n in range(len(A_)):
      for comb in itertools.combinations(A_, n+1):
        lists.append(list(comb))
    for lis in lists:
      _sum = sum(lis)
      if _sum == S:
        val += 1
print(val % 998244353)

Submission status: Wrong Answer

Solution code:
from numpy import zeros

mod = 998244353

N, S, *A = map(int, open(0).read().split())

dp = zeros(S + 1, dtype=int)
ans = 0
for i, a in enumerate(A, 1):
    if a <= S:
        T = dp.copy()
        dp[a:] += T[:S + 1 - a]
        dp[a] += i
        
    ans += dp[S]
    ans %= mod
    
print(ans)

Submission status: Wrong Answer

Solution code:
from numpy import zeros

mod = 998244353


N, S, *A = map(int, open(0).read().split())

dp = zeros(S + 1, dtype="int32")
ans = 0
for i, a in enumerate(A, 1):
    if a <= S:
        dp[a:] += dp[:S + 1 - a]
        dp[a] += i

    ans += dp[-1]
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
from numpy import zeros

mod = 998244353


N, S, *A = map(int, open(0).read().split())

dp = zeros(S + 1, dtype=int)
ans = 0
for i, a in enumerate(A, 1):
    if a <= S:
        dp[a:] += dp[:S + 1 - a]
        dp[a] += i

    ans += dp[-1]
    ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

MOD = 998244353
N, S = lr()
A = lr()
dp = np.array([0] * (S+1), dtype=np.int64)
answer = 0
for a in A:  
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    dp[a:] += prev[:-a]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

MOD = 998244353
N, S = lr()
A = lr()
dp = np.array([0] * (S+1))
answer = 0
for a in A:  
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    dp[a:] += prev[:-a]
    answer += dp[-1] # その位置Rとした時

print(answer % MOD)
# 26

Submission status: Wrong Answer

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

L = 0
R = 1
L_max = N-1
R_max = N
count = 0

while L <= L_max:
    while sum(A[L:R]) <= S:
#         print(L,R)

        if sum(A[L:R]) == S:
#             print("HIT!",L,R,(L+1) * (N-R+1))
#             count += N - (R-1-L)
            count += (L+1) * (N-R+1)
            break

        if R <= R_max and L <= L_max:
            if sum(A[L:R]) < S:
                R += 1
            else:
                L += 1
        else:
            break
    L += 1


print(count % 998244353)

Submission status: Wrong Answer

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

L = 0
R = 1
L_max = N-1
R_max = N
count = 0

while L <= L_max:
    while sum(A[L:R]) <= S:
        print(L,R)

        if sum(A[L:R]) == S:
            print("HIT!",L,R,(L+1) * (N-R+1))
#             count += N - (R-1-L)
            count += (L+1) * (N-R+1)
            break

        if R <= R_max and L <= L_max:
            if sum(A[L:R]) < S:
                R += 1
            else:
                L += 1
        else:
            break
    L += 1


print(count % 998244353)

Submission status: Wrong Answer

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

L = 0
R = 1
L_max = N-1
R_max = N
count = 0

while L <= L_max:
    while sum(A[L:R]) <= S:

        if sum(A[L:R]) == S:
            count += N - (R-1-L)
            break

        if R <= R_max and L <= L_max:
            if sum(A[L:R]) < S:
                R += 1
            else:
                L += 1
        else:
            break
    L += 1


print(count % 998244353)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
class FastModuloTransform():
    def __init__(self, omega, n, mod):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega, mod - 2, mod)

    def _bit_reverse_(self, d):
        n = len(d)
        ns = n >> 1
        nss = ns >> 1
        ns1 = ns + 1
        i = 0
        for j in range(0, ns, 2):
            if j < i:
                d[i], d[j] = d[j], d[i]
                d[i + ns1], d[j + ns1] = d[j + ns1], d[i + ns1]
            d[i + 1], d[j + ns] = d[j + ns], d[i + 1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d

    def _fmt_(self, A, base):
        halfpow = pow(base, self.n // 2, self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base, n, self.mod)
            wk = 1
            for j in range(m):
                for i in range(j, self.n, 2 * m):
                    U = A[i]
                    V = (A[i + m] * wk) % self.mod
                    A[i] = (U + V) % self.mod
                    A[i + m] = (U + V * halfpow) % self.mod
                wk = (wk * w) % self.mod
            m <<= 1
        return A

    def fmt(self, f):
        A = f + [0] * (self.n - len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A, self.omega)
        return F

    def ifmt(self, F):
        A = F + [0] * (self.n - len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n, self.mod - 2, self.mod)
        f = [(e * nrev) % self.mod for e in self._fmt_(A, self.rev)]
        return f

    def convolute(self, f, g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s * t) % self.mod for s, t in zip(F, G)]
        h = self.ifmt(H)
        return h

fmt = FastModuloTransform(299814, 2**12, 998244353)

MOD = 998244353

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

F = [0]
res = 0

for i in range(N):
    F[0] += 1
    f = [0 for _ in range(A[i] + 1)]
    f[0] = 1
    f[-1] = 1
    F = fmt.convolute(F, f)
    F = F[:S + 1]
    res += F[S]
    res %= MOD

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,S = map(int,input().split())
list = list(map(int,input().split()))
A = np.zeros((N+1,S+1,3),dtype=np.int16)
A[0][0][0] = 1

Submission status: Wrong Answer

Solution code:
import numpy as np
N,S = map(int,input().split())
A = np.zeros((N+1,S+1,3),dtype=np.int16)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,S = map(int,input().split())
list = np.int32(input().split())

Submission status: Wrong Answer

Solution code:
import numpy as np
N,S = map(int,input().split())
list = np.int32(input().split())
A = [[[0,0,0]for i in range(S+1)]for j in range(N+1)]
A[0][0][0] = 1

Submission status: Wrong Answer

Solution code:
N,S = map(int,input().split())
list = list(map(int,input().split()))
A = [[[0,0,0]for i in range(S+1)]for j in range(N+1)]
A[0][0][0] = 1

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,S = map(int,input().split())
list = list(map(int,input().split()))
A = [[[0,0,0]for i in range(S+1)]for j in range(N+1)]
A[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        A[i+1][j][0] += A[i][j][0]
        A[i+1][j][1] += A[i][j][0] + A[i][j][1]
        A[i+1][j][2] += A[i][j][0] + A[i][j][1] + A[i][j][2]
        if list[i] + j <= S:
            A[i+1][list[i]+j][1] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][2] += A[i][j][0] + A[i][j][1]
print(A[N][S][2])

Submission status: Wrong Answer

Solution code:
import numpy as np

Submission status: Wrong Answer

Solution code:
class FastModuloTransform():
    def __init__(self, omega, n, mod):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega, mod - 2, mod)

    def _bit_reverse_(self, d):
        n = len(d)
        ns = n >> 1
        nss = ns >> 1
        ns1 = ns + 1
        i = 0
        for j in range(0, ns, 2):
            if j < i:
                d[i], d[j] = d[j], d[i]
                d[i + ns1], d[j + ns1] = d[j + ns1], d[i + ns1]
            d[i + 1], d[j + ns] = d[j + ns], d[i + 1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d

    def _fmt_(self, A, base):
        halfpow = pow(base, self.n // 2, self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base, n, self.mod)
            wk = 1
            for j in range(m):
                for i in range(j, self.n, 2 * m):
                    U = A[i]
                    V = (A[i + m] * wk) % self.mod
                    A[i] = (U + V) % self.mod
                    A[i + m] = (U + V * halfpow) % self.mod
                wk = (wk * w) % self.mod
            m <<= 1
        return A

    def fmt(self, f):
        A = f + [0] * (self.n - len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A, self.omega)
        return F

    def ifmt(self, F):
        A = F + [0] * (self.n - len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n, self.mod - 2, self.mod)
        f = [(e * nrev) % self.mod for e in self._fmt_(A, self.rev)]
        return f

    def convolute(self, f, g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s * t) % self.mod for s, t in zip(F, G)]
        h = self.ifmt(H)
        return h

fmt = FastModuloTransform(299814, 2**12, 998244353)

MOD = 998244353

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

F = [0]
res = 0

for i in range(N):
    F[0] += 1
    f = [0 for _ in range(A[i] + 1)]
    f[0] = 1
    f[-1] = 1
    F = fmt.convolute(F, f)
    res += F[S]
    res %= MOD

print(res)

Submission status: Wrong Answer

Solution code:
class FastModuloTransform():
    def __init__(self, omega, n, mod):
        self.n = n
        self.omega = omega
        self.mod = mod
        self.rev = pow(omega, mod - 2, mod)

    def _bit_reverse_(self, d):
        n = len(d)
        ns = n >> 1
        nss = ns >> 1
        ns1 = ns + 1
        i = 0
        for j in range(0, ns, 2):
            if j < i:
                d[i], d[j] = d[j], d[i]
                d[i + ns1], d[j + ns1] = d[j + ns1], d[i + ns1]
            d[i + 1], d[j + ns] = d[j + ns], d[i + 1]
            k = nss
            i ^= k
            while k > i:
                k >>= 1
                i ^= k
        return d

    def _fmt_(self, A, base):
        halfpow = pow(base, self.n // 2, self.mod)
        n = self.n
        m = 1
        while n > 1:
            n >>= 1
            w = pow(base, n, self.mod)
            wk = 1
            for j in range(m):
                for i in range(j, self.n, 2 * m):
                    U = A[i]
                    V = (A[i + m] * wk) % self.mod
                    A[i] = (U + V) % self.mod
                    A[i + m] = (U + V * halfpow) % self.mod
                wk = (wk * w) % self.mod
            m <<= 1
        return A

    def fmt(self, f):
        A = f + [0] * (self.n - len(f))
        self._bit_reverse_(A)
        F = self._fmt_(A, self.omega)
        return F

    def ifmt(self, F):
        A = F + [0] * (self.n - len(F))
        self._bit_reverse_(A)
        nrev = pow(self.n, self.mod - 2, self.mod)
        f = [(e * nrev) % self.mod for e in self._fmt_(A, self.rev)]
        return f

    def convolute(self, f, g):
        F = self.fmt(f)
        G = self.fmt(g)
        H = [(s * t) % self.mod for s, t in zip(F, G)]
        h = self.ifmt(H)
        return h

fmt = FastModuloTransform(299814, 2**12, 998244353)

MOD = 998244353

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

F = [0]
res = 0

for i in range(N):
    F[0] += 1
    f = [0 for _ in range(A[i] + 1)]
    f[0] = 1
    f[-1] = 1
    F = fmt.convolute(F, f)
    res += F[S]

print(res)

Submission status: Wrong Answer

Solution code:
n,s = [int(c) for c in input().split()]
a = [int(c) for c in input().split()]
# t[i][j] : 0<=r<...,<l=iについて和がsになるようなf(r,l)の和
t = [[0]*(s+1) for _ in range(n)]
if a[0]<=s:
    t[0][a[0]] = 1
for i in range(n):
    t[i][0] = i+2
for i in range(1,n):
    for j in range(1,s+1):
        tt = t[i-1][j]
        if j-a[i]>=0:
            tt += t[i-1][j-a[i]]
        t[i][j] = tt
print(sum(t[i][s] for i in range(n)))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,s = [int(c) for c in input().split()]
a = [int(c) for c in input().split()]
# t[i][j] : 0<=r<...,<l=iについて和がsになるようなf(r,l)の和
t = [[0]*(s+1) for _ in range(n)]
if a[0]<=s:
    t[0][a[0]] = 1
for i in range(n):
    t[i][0] = i+2
for i in range(1,n):
    for j in range(1,s+1):
        tt = 0
        if t[i-1][j]>0:
            tt += t[i-1][j]
        if j-a[i]>=0:
            tt += t[i-1][j-a[i]]
        t[i][j] = tt
print(sum(t[i][-1] for i in range(n)))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
MOD = 998244353


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

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

    dp[0][0][0] = 1

    for i in range(0, N):
        for s in range(0, S+1):

            if s == 0:
                dp[i+1][s][0] = 1
            else:
                dp[i+1][s][0] = 0

            if s - A[i] >= 0:
                dp[i+1][s][1] = dp[i][s][1] + dp[i][s][0] + dp[i][s-A[i]][1] + dp[i][s-A[i]][0] % MOD
                dp[i+1][s][2] = dp[i][s][2] + dp[i][s][1] + dp[i][s][0] + dp[i][s-A[i]][1] + dp[i][s-A[i]][0] % MOD
            else:
                dp[i+1][s][1] = dp[i][s][1] + dp[i][s][0] % MOD
                dp[i+1][s][2] = dp[i][s][2] + dp[i][s][1] + dp[i][s][0] % MOD

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


solve()

Submission status: Wrong Answer

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd
import sys
from decimal import *
input=lambda :sys.stdin.readline().rstrip()

N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
dp=[defaultdict(int) for i in range(S+1)]
lst=set()
if A[0]<=S:
    dp[A[0]][0]+=1
    lst.add(A[0])
count=0
for n in range(1,N):
    nlst=set()
    for i in lst:
        b=i+A[n]
        if b<=S:
            for a in dp[i]:
                dp[b][a]+=dp[i][a]
            if not b in lst:
                nlst.add(b)
    if A[n]<=S:
        dp[A[n]][n]+=1
        lst.add(A[n])
    lst|=nlst

    for i in dp[S]:
        count+=(i+1)*dp[S][i]
        count%=mod
#print(dp)
print(count)