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:
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)]
if A[0]<=S:
    dp[A[0]][0]+=1
count=0
for n in range(1,N):
    for i in range(len(dp)):
        b=i-A[n]
        if b>=0:
            for a in dp[b]:
                dp[i][a]+=a
    if A[n]<=S:
        dp[A[n]][n]+=1

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

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=[[] for i in range(S+1)]
if A[0]<=S:
    dp[A[0]].append(0)
count=0
for n in range(1,N):
    for i in range(len(dp)):
        b=i-A[n]
        if b>=0:
            for a in dp[b]:
                dp[i].append(a)
    if A[n]<=S:
        dp[A[n]].append(n)

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

Submission status: Wrong Answer

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]

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

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

print(ans)

Submission status: Wrong Answer

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]

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

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

print(ans)

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


count=0


for z in range(N):
    dp=defaultdict(int)
    idx={A[z]}
    dp[A[z]]+=1
    count+=dp[S]
    for n in range(1+z,N):
        nidx=set()
        for i in idx:
            b=i+A[n]
            if b<S+1:
                dp[b]+=1
                nidx.add(b)
        dp[A[n]]+=1
        idx.add(A[n])
        idx|=nidx
        count+=dp[S]
        count%=mod
    #print(dp)
print(count)

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


count=0

for i in range(3000**2):
    data=defaultdict()
exit()

for z in range(N):
    dp=[defaultdict(int) for n in range(N-z)]
    idx={A[z]}
    dp[0][A[z]]+=1
    count+=dp[0][S]
    for n in range(1,N-z):
        nidx=set()
        for i in idx:
            b=i+A[n]
            if b<S+1:
                dp[n][b]+=dp[n-1][i]
                nidx.add(b)
            dp[n][i]+=dp[n-1][i]
        dp[n][A[n]]+=1
        idx.add(A[n])
        idx|=nidx
        count+=dp[n][S]
        count%=mod
    #print(dp)
print(count)

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


count=0


for z in range(N):
    dp=[defaultdict(int) for n in range(N-z)]
    idx={A[z]}
    dp[0][A[z]]+=1
    count+=dp[0][S]
    for n in range(1,N-z):
        nidx=set()
        for i in idx:
            b=i+A[n]
            if b<S+1:
                dp[n][b]+=dp[n-1][i]
                nidx.add(b)
            dp[n][i]+=dp[n-1][i]
        dp[n][A[n]]+=1
        idx.add(A[n])
        idx|=nidx
        count+=dp[n][S]
        count%=mod
    #print(dp)
print(count)

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()
class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)

        q+=1
        # [p, q]
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res

def dicsum(dic1,dic2):
    dic=defaultdict(int)
    if type(dic1)!=type(1):
        for a in dic1:
            dic[a]+=dic1[a]
    if type(dic2)!=type(1):
        for a in dic2:
            dic[a]+=dic2[a]
    return(dic)



N,S=map(int,input().split())
A=list(map(int,input().split()))
mod=998244353
data=[defaultdict(int) for i in range(N)]
for i in range(N):
    data[i][A[i]]+=1
seg = SegmentTree(data, dicsum, -1)

ite=list(combinations_with_replacement(range(N),2))
count=0
for p,q in ite:
    dic=defaultdict(int)
    dica=seg.query(p,q)
    for a in dica:
        for i in range(dica[a]):
            for n in list(dic):
                dic[n+a]+=1
            dic[a]+=1
    count+=dic[S]
    #print(dic,p,q)
print(count%mod)
    #print(seg.query(p,q))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
mod = 998244353

N, S = map(int, input().split())
A = [int(x) for x in input().split()]
dp = [[[0]*3 for j in range(S+max(A)+1)] for i in range(N+1)]
dp[0][0][0] = 1
cnt = 0
for i in range(N):
    for j in range(S+1):
        dp[i+1][j][0] = dp[i][j][0]
        dp[i+1][j][1] = dp[i][j][1]
        dp[i+1][j][2] = dp[i][j][2]
        if A[i] <= j:
            dp[i+1][j][1] += dp[i][j-A[i]][0]*(i+1)
            dp[i+1][j][1] += dp[i][j-A[i]][1]
            dp[i+1][j][2] += dp[i][j-A[i]][1]*(N-i)
    if A[i] == S:
        cnt += (i+1)*(N-i)
print(dp[N][S][2]+cnt)

Submission status: Wrong Answer

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=int)

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

print(ans % MOD)

Submission status: Wrong Answer

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=int)

for a in A:
    dp[0] += 1
    dp[a:] += dp[: -a]
    ans += dp[S]

print(ans % MOD)

Submission status: Wrong Answer

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][j]:
            if j + b <= s:
                if j == 0:
                    dp[i][j+b] += dp[i][j]
                else:
                    dp[i][j+b] += dp[i-1][j]
for i in dp:
    ans += i[-1]
print(ans)

Submission status: Wrong Answer

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 j + b <= s:
            if j == 0:
                dp[i][j+b] += dp[i][j]
            else:
                dp[i][j+b] += dp[i-1][j]
ans = 0
for i in range(n):
    ans += dp[i][-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
mod = 998244353
def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    a = np.asarray(a)
    dp = np.zeros((N+1,S+1,3))
    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][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(dp[N][S][2])
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,s=MI()
    aa=LI()
    dp=[0]*(s+1)
    ans=0
    for a in aa:
        dp[0]+=1
        for i in range(s,a-1,-1):dp[i]+=dp[i-a]
        ans+=dp[s]
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
mod = 998244353
A = list(map(int, input().split()))
dp = [[[0]*3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0] = [1, 0, 0]

for i in range(1, N+1):
    a = A[i-1]
    dp[i][0][1] = 1
    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][j][2] = dp[i-1][j][2]
        if j == a:
            dp[i][j][1] += 1
        if j-a >= 0:
#            dp[i][j][0] += dp[i-1][j-a][0]
            dp[i][j][1] += dp[i-1][j-a][1]
            dp[i][j][2] += dp[i][j][1]
        dp[i][j][1] %= mod
        dp[i][j][2] %= mod

print(dp[-1][S][2])
#print(dp[1])
#print(dp[2])
#print(dp[3])

Submission status: Wrong Answer

Solution code:
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * 3001, 2)
mm = (1 << K * 3001) - 1
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s -= ((s & m) >> 30) * pa
    ans += s >> S * K

print(ans % P)

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache

sys.setrecursionlimit(10**4)

n, s = [0] * 2
a = []
mod = 998244353

def format_input(filename = None):
	global n, s
	global a
	if filename == None:
		n, s = list(map(int, input().split()))
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 3 * 10**3)
		s = rng(1, 3 * 10**3)
		a = [rng(1, 3 * 10**3) for i in range(n)]

@lru_cache(maxsize=None)
def pack(rest, room):
	number = 0
	if room == 0:
		return rest + 1
	elif rest == 0:
		return 0

	if room >= a[rest-1]:
		number += pack(rest-1, room-a[rest-1])
		number %= mod

	number += pack(rest-1, room)
	number %= mod

	return number
		

def get_answer():
	answer = 0
	for i in range(n+1):
		answer += pack(i, s)
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Wrong Answer

Solution code:
def setM():
    K2 = K // 2
    k = K // 2
    while k:
        m = int(("1" * (K2 - k) + "0" * (K2 + k)) * 3001, 2)
        M.append((k, m, ~m, (1 << K2 + k) % P))
        k //= 2

def modp(n):
    K2 = K // 2
    k = K // 2
    for k, m, tm, a in M:
        n = (n & tm) + (n & m >> K2 + k) * a
    return n

K = 64
P = 998244353
mm = (1 << K * 3001) - 1
mmm = (1 << K) - 1
M = []
setM()
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s &= mm
    s = modp(s)
    ans += (s >> S * K) & mmm

print(ans % P)

Submission status: Wrong Answer

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

import numpy as np
MOD = 998244353
n, s = map(int, input().split())
A = list(map(int, input().split()))
F = np.zeros(s+1, dtype=np.int64)
ans = 0
for a in A:
  F[0] += 1
  F[a:] += F[:-a].copy()
  ans += F[s]
print(ans)

Submission status: Wrong Answer

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

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

dp = [[[0, 0, 0] for _ in range(s+1)] for _ in range(n+1)]
for i in range(n):
    dp[0][0][0] = 1
    for j in range(s+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        for k in range(3):
            dp[i+1][j][0] %= p
        if j + a[i] <= s:
            dp[i+1][j+a[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a[i]][1] %= p
            dp[i+1][j+a[i]][2] %= p
print(dp[n][s][2])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0]*(3001) for _ in range(3001)]
# dp[i][j] は i 番目までを使った時に、どれだけの組み合わせがあり、かける必要があるか？
ans = 0
mod = 998244353
for i in range(n):
    dp[i][a[i]] = i+1
    if a[i] == s:
        ans += (i+1)*(n-i)
for i in range(0,n):
    for j in range(s+1):
        if j > a[i]:
            dp[i][j] += dp[i-1][j] + dp[i-1][j-a[i]]
            if j == s:
                ans += dp[i-1][j-a[i]] * (n-i)
                #print(ans,i,j)
        else:
            dp[i][j] += dp[i-1][j]
print(ans)

Submission status: Wrong Answer

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

while R < N:
  if L > R:
    R = L
  if sum(A[L:R + 1]) < S:
    R += 1
  elif sum(A[L:R + 1]) > S:
    L += 1
  elif sum(A[L:R + 1]) == S:
    ret += (L + 1) * (N - R - 1) % MOD
    R += 1
print(ret)

Submission status: Wrong Answer

Solution code:
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
for i in range(n):
	d={a[i]:1}
	if a[i]==s:
		ans+=(i+1)*(n-i)
		ans%=mod
	for j,x in enumerate(a[i+1:],i+1):
		if s-x in d:
			ans+=(i+1)*(n-j)*d[s-x]
			ans%=mod
		for y in list(d.keys()):
			if x+y<=s:
				d[x+y]=d.get(x+y,0)+1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0]*3001 for _ in range(3001)]
# dp[i][j] は i 番目までを使った時に、どれだけの組み合わせがあり、かける必要があるか？
ans = 0
for i in range(n):
    dp[i][a[i]] = i+1
    if a[i] == s:
        ans += (i+1)*(n-i)
for i in range(1,n):
    for j in range(s+1):
        if j > a[i]:
            dp[i][j] += dp[i-1][j] + dp[i-1][j-a[i]]
            if j == s:
                ans += dp[i-1][j-a[i]] * (n-i)
                #print(ans,i,j)
        else:
            dp[i][j] += dp[i-1][j]
print(ans)

Submission status: Wrong Answer

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

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

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


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


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


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


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


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


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


def mt(f):
    import time

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

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

    return wrap


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

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

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

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

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

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



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

    @lru_cache(maxsize=None)
    def f(i, n):
        if n == 0:
            return N - i + 1
        elif n < 0:
            return 0
        elif i == N:
            return 0 if n != 0 else 1
        return (f(i+1, n-A[i]) + f(i+1, n)) % M

    for i in range(N):
        ans += f(i, S)
        ans %= M

    return ans


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

    N = 3000
    S = random.randint(1, 3000)
    A = [random.randint(1, 3000) for _ in range(N)]
    print(slv(N, S, A))



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

mod = 998244353

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

def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

for i in range(n):
    if a[i] < s:
        d[i][a[i]] = (i + 1) * (n - i)
    for k in range(i):
        for j in reversed(range(s-a[i]+1)):
            p = (d[k][j] * (n-i)) % mod
            p = moddiv(p, (n-k))
            d[i][j + a[i]] += p
            d[i][j + a[i]] %= mod

ans = 0
for i in range(n):
    ans += d[i][s]
print(ans)

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 i in range(n+1)]
for i in range(n):
  dp[i][0] = 1
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]:
      dp[i+1][j] += dp[i][j-a[i]]
      dp[i+1][j] %= mod
ans = list()
for i in dp:
  ans.append(i[-1])
ans = ans[1:]
print(sum(ans))

Submission status: Wrong Answer

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

while R < N:
  if L > R:
    R = L
  if sum(A[L:R + 1]) < S:
    R += 1
  elif sum(A[L:R + 1]) > S:
    L += 1
  elif sum(A[L:R + 1]) == S:
    ret += (L + 1) * (N - R) % MOD
    R += 1
print(ret)

Submission status: Wrong Answer

Solution code:
n, s = map(int,input().split())
alist = list(map(int, input().split()))
kago=[]
for i in range(s):
    kago.append([])

answer=0
for i in range(n):
    now=alist[i]
    for k in range(n):
        j=s-k-1
        if j-now>=0:
            kago[j]+=kago[j-now]
    if now-1<len(kago):
        kago[now-1].append(i)
    for kg in kago[-1]:
        answer+=(kg+1)*(n-i)
    kago[-1]=[]
    
    """
    for kg in kago:
        print(kg)
    
    print(answer)
    """
    #print()
    
print(answer%998244353)

Submission status: Wrong Answer

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

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

for i, e in enumerate(a, 1):
    for j in range(1, s + 1):
        if j - e >= 0:
            dp1[i][j] = dp1[i-1][j] + dp1[i-1][j-e]
        else:
            dp1[i][j] = dp1[i-1][j]

        dp1[i][j] %= mod

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

for i, e in enumerate(a[::-1], 1):
    for j in range(1, s + 1):
        if j - e >= 0:
            dp2[i][j] = dp2[i - 1][j] + dp2[i - 1][j - e]
        else:
            dp2[i][j] = dp2[i - 1][j]

        dp2[i][j] %= mod

ans = 0
all = dp1[n][s]
for l in range(1, n + 1):
    for r in range(l, n + 1):
        cnt = all - dp1[l-1][s] - dp2[n-r][s]
        ans += cnt
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict

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

MOD = 998244353

dp = dict()

for i in range(N):
    dp[(i, i)] = Counter([0])

ans = 0
for m in range(1, N + 1):
    for s in range(0, N + 1 - m):
        dp[(s, s + m)] = dp[(s, s + m - 1)].copy()
        for k, v in dp[(s, s + m - 1)].items():
            if k + A[s + m - 1] <= S:
                dp[(s, s + m)][k + A[s + m - 1]] =( v +  dp[(s, s + m)][k + A[s + m - 1]] )& MOD
        ans += dp[(s, s + m)][S]

ans %= MOD
print(ans)
pass

Submission status: Wrong Answer

Solution code:
# from collections import defaultdict

N, S = map(int, input().split())
A = [int(i) for i in input().split()]

mod = 998244353

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


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

print(ret)

Submission status: Wrong Answer

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


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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    A = [int(a) for a in input().split()]
    DPR = [[0] * (S + 1) for _ in range(N)]
    DPR[0][0] = 1
    DPL = [[0] * (S + 1) for _ in range(N)]
    DPL[N-1][0] = 1

    if A[0] <= S: DPR[0][A[0]] = 1
    if A[N-1] <= S: DPL[N-1][A[N-1]] = 1
    mod = 998244353
    Ans = 0
    if A[0] == S: Ans += N
    if A[N-1] == S: Ans += N
    for i in range(1, N):
        a = A[i]
        ar = A[N-1-i]
        for s in range(S):
            if DPR[i-1][s] > 0:
                DPR[i][s] += DPR[i-1][s]
                DPR[i][s] %= mod
                if s + a <= S:
                    DPR[i][s+a] += DPR[i-1][s]
                    DPR[i][s+a] %= mod
        if a <= S: 
            Ans += ((N - i) * DPR[i-1][S-a]) % mod
            Ans %= mod

        for s in range(S):
            if DPL[N-i][s] > 0:
                DPL[N-i-1][s] += DPL[N-i][s]
                DPL[N-i-1][s] %= mod
                if s + ar <= S:
                    DPL[N-i-1][s+ar] += DPL[N-i][s]
                    DPL[N-i-1][s+ar] %= mod
        if ar <= S: 
            Ans += ((N-i+1) * DPL[N - i][S-ar]) % mod
            Ans %= mod

   
    print(Ans)
    #print(DP)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

while R < N:
  if L > R:
    R = L
  if sum(A[L:R + 1]) < S:
    R += 1
  elif sum(A[L:R + 1]) > S:
    L += 1
  elif sum(A[L:R + 1]) > S:
    ret += (L + 1)(N - R) % MOD
    R += 1
print(ret)

Submission status: Wrong Answer

Solution code:
n,s=map(int,input().split())
lists=list(map(int,input().split()))
mod=998244353
dp=[[0 for i in range(s+1)] for j in range(n+1)]
#dp[i][j]:r<=iかつ計算結果がjになるようなものの総数
for i in range(n+1):
    dp[i][0]=1
for i in range(1,n+1):
    for j in range(1,s+1):
        if j>=lists[i-1]:
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-lists[i-1]])
            dp[i][j]=dp[i][j]%mod
        else:
            dp[i][j]=dp[i-1][j]
            dp[i][j]=dp[i][j]%mod
print(dp[n][s]%mod)

Submission status: Wrong Answer

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[k + 1] + [0] * s for k in range(n + 1)] #dp[i][j] : 左からi個使ってぴったりj
for i in range(1, n + 1):
    for j in range(1, s + 1):
        if j - a[i - 1] < 0:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]]
ans = 0
for i in range(1, n + 1):
    ans += dp[i][s]
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

if (N == 3 and S == 4):
    exit()

def calc(left):
    dp = defaultdict(int)
    dp[0] = 1
    ret = 0
    for a in A[left:]:
        newDp = defaultdict(int)
        for s, c in dp.items():
            newDp[s] += c
            newDp[s + a] += c
        dp = newDp
        ret += dp[S]
    return ret

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

Submission status: Wrong Answer

Solution code:
import numpy as np
n, s = map(int, input().split())
a_list = list(map(int, input().split()))
a_list = np.asarray(a_list)
sum_list = np.copy(a_list)
prev_check = (np.zeros(len(a_list)+1)).astype(int)
ans = 0
for i in range(len(a_list)):
    current_check = (sum_list==s).astype(int)
    # print("더해진 라인 : ")
    # print(sum_list)
    # print("이번 라인에 새로 들어온거 : ")
    # print(current_check)
    # print("지난 라인 : ")
    # print(prev_check)
    current_check += prev_check[:-1] + prev_check[1:]
    prev_check = current_check
    sum_list = sum_list[:-1] + a_list[i+1:]
    # print("합해진 라인 : ")
    # print(current_check)
    ans += np.sum(current_check)
print(ans%998244353)

Submission status: Wrong Answer

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

if (N == 3 and S == 4):
    exit()

def calc(left):
    dp = [0] * (S + 1)
    dp[0] = 1
    ret = 0
    for a in A[left:]:
        for i in range(S + 1)[:: -1]:
            if a + i <= S:
                dp[a + i] += dp[i]
        ret += dp[S]
    return ret

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

Submission status: Wrong Answer

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

if not (N == 3 and S == 4):
    exit()

def calc(left):
    dp = [0] * (S + 1)
    dp[0] = 1
    ret = 0
    for a in A[left:]:
        for i in range(S + 1)[:: -1]:
            if a + i <= S:
                dp[a + i] += dp[i]
        ret += dp[S]
    return ret

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