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: Runtime Error

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

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

import sys
input = sys.stdin.readline

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


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

MOD = 998244353
INF = float('inf')

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

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

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

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

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

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

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

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

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

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

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

dp = [[[0,0] for s in range(S+2)] for r in range(N+1)]

for s in range(S):
  for r in range(N):
    if s == 0:
      dp[r][s] = [1,r+2]
    if r == 0:
      if s == l[r]:
        dp[r][s] = [1,1]
      else:
        dp[r][s] = [0,0]
    else:
      dp[r][s] = [dp[r-1][s][0] + dp[r-1][s][1] + dp[r-1][s-l[r]][1],dp[r-1][s][1]+dp[r-1][s-l[r]][1]]


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

Submission status: Runtime Error

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[0]] = 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: Runtime Error

Solution code:
import numpy as np
n,s=map(int,input().split())
t=np.zeros(s+1)
m=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(n):
    t[a[i]:]+=t[:-a[i]]
    if a[i]<s:
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))

Submission status: Runtime Error

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

# 累積和、dp、しゃくとり
MOD = 998244353
N, S = lr()
A = lr()
# dp[k][j] kから始めた合計の個数
dp = np.array([[0] * 3000 for _ in range(N)])
dp[:, 0] = 1
answer = 0
cur = [0] * (N)
#print(dp)
for i, a in enumerate(A):
    # iが現在地
    for j in range(i+1):
        prev = dp[j].copy()
        dp[j][a:] += prev[:-a]
        temp = dp[j][S] - cur[j]
        answer += temp * (N-i)
        cur[j] = dp[j][S]

print(answer % MOD)

Submission status: Runtime Error

Solution code:
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[[0 for i in range(S+1)] for i in range(N+1)] for k in range(N+1)]
for i in range(1,N+1):
    for j in range(i):
        dp[i][j][0] = 1
B = [0]
for i in range(1,N+1):
    for j in range(i,N+1):
        n = len(B)
        for k in range(S+1):
            dp[i][j][k] += dp[i][j-1][k]
          if Bk + A[j-1] <= S:
              dp[i][j][k+A[j-1]] += dp[i][j-1][k]
mod = 998244353
ans = 0
for i in range(1,N+1):
    for j in range(i,N+1):
        ans += dp[i][j][S] % mod
        ans = ans % mod
print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n,s=map(int,input().split())
t=np.zeros(s+1)
m=10**9+7
a=list(map(int,input().split()))
ans=0
for i in range(n):
    t[a[i]:]+=t[:-a[i]]
    t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))

Submission status: Runtime Error

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

# 累積和、dp、しゃくとり
MOD = 998244353
N, S = lr()
A = lr()
# dp[k][j] kから始めた合計の個数
dp = np.array([[0] * 3000 for _ in range(N)])
dp[:, 0] = 1
answer = 0
cur = [0] * (N)
#print(dp)
for i, a in enumerate(A):
    # iが現在地
    for j in range(i+1):
        prev = dp[j].copy()
        dp[j][a:] += prev[:-a]
        temp = dp[j][S] - cur[j]
        answer += temp * (N-i)
        z = int(dp[j][S])
        cur[j] = z
        #print(i, j, answer, temp, dp[j][S])
    answer %= MOD

print(answer % MOD)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

dp  = {0:(0,0)}

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

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 998244353
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inpl(): return list(map(int, sys.stdin.readline().split()))


def inpl_str(): return list(sys.stdin.readline().split())


N, S = inpl()
aa = inpl()

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

ans = 0
for i, a in enumerate(aa):
    ans += dp[S-a] * (N-i) % mod
    ans %= mod

    for s in reversed(range(a, S)):
        if s == a:
            dp[s] += i+1
        else:
            dp[s] += dp[s-a]
        dp[s] %= mod


print(ans)

Submission status: Runtime Error

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

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

import sys
input = sys.stdin.readline

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


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

MOD = 998244353
INF = float('inf')

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

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

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

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

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

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

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

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

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

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

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

from functools import lru_cache
@lru_cache(maxsize=None)

def f(r,s):
  if s == 0:
    return (1,r+2)
  if r == 0:
    if s == l[r]:
      return (1,1)
    else:
      return (0,0)
  else:
    return (f(r-1,s)[0] + f(r-1,s)[1] + f(r-1,s-l[r])[1],f(r-1,s)[1]+f(r-1,s-l[r])[1])

print(f(N-1,S)[0])

Submission status: Runtime Error

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

# 累積和、dp、しゃくとり
MOD = 998244353
N, S = lr()
A = lr()
# dp[k][j] kから始めた合計の個数
dp = np.array([[0] * 3000 for _ in range(N)])
dp[:, 0] = 1
answer = 0
cur = [0] * (N)
for i, a in enumerate(A):
    # iが現在地
    for j in range(i+1):
        dp[j][a:] += dp[j][:-a]
        temp = dp[j][S] - cur[j]
        answer += temp * (N-i)
        cur[j] = dp[j][S]
        #print(i, j, answer, temp, dp[j][S])
    answer %= MOD

print(answer % MOD)

Submission status: Runtime Error

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

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

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

print(ans)

Submission status: Runtime Error

Solution code:
from numpy import *
M=998244353
N,S,*A=map(int,open(0).read().split())
a=0
f = np.zeros(S+1, np.int64)
for b in As:
  f[0]+=1
  f[b:] += f[:-b].copy()
  f%=M
  a+=f[S]
print(a%M)

Submission status: Runtime Error

Solution code:
N, S = input().split(" ")
N, S = int(N), int(S)
_list = []
for _ in range(0, N):
    _list.append(int(input()))

print(sum(_list))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    mod=998244353
    dp=[[0]*(s+1) for _ in range(n+1)]
    dp[0][0]=1
    for i in range(1,n+1):
        for j in range(s+1):
            a=A[n-i]
            if j-a>0:
                dp[i][j]=(dp[i-1][j]+dp[i-1][j-a])%mod
            elif j==a:
                dp[i][j]=(dp[i-1][j]+i)%mod
            else:
                dp[i][j]=dp[i-1][j]
    ans=0
    for i in range(1,n+1):
        a=A[i-1]
        ans=(ans+dp[n-i][s-a]*i)%mod
    print(ans)
if __name__ == '__main__':
    main()