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:
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] += p[:-x[i-1],0] + p[:-x[i-1],1]
    m[x[i]:,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(p[S,2]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
x = [0, *x]
 
# 状態リストを作成
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] += p[:-x[i],0] + p[:-x[i],1]
    m[x[i]:,2] += p[:-x[i],0] + p[:-x[i],1]

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

Submission status: Runtime Error

Solution code:
import numpy as np

N, S = map(int, input().split())
x = [int(x) for x in input().split()]
x = [0, *x]
 
# 状態リストを作成
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] += p[:-x[i],0] + p[:-x[i],1]
    m[x[i]:,2] += p[:-x[i],0] + p[:-x[i],1]

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

Submission status: Runtime Error

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

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

dp = np.array([[0]*(s+1) 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: Runtime Error

Solution code:
N, S = map(int, input().split())
x = [int(x) for x in input().split()]
x = [0, *x]
 
# 状態リストを作成
m = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
m[0][0][0] = 1
 
for i in range(1,N+1):
    
    for k in range(S+1):

        # x を含めない
        m[i][k][0] += m[i-1][k][0] # まだ開始しない
        m[i][k][1] += m[i-1][k][0] + m[i-1][k][1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
        m[i][k][2] += m[i-1][k][0] + m[i-1][k][1] + m[i-1][k][2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

        # x を含める場合
        if k - x[i] >= 0:
            m[i][k][1] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
            m[i][k][2] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
        
        m[i][k][0] = m[i][k][0] % 998244353
        m[i][k][1] = m[i][k][1] % 998244353
        m[i][k][2] = m[i][k][2] % 998244353
            
print(m[N][S][2])

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
x = [int(x) for x in input().split()]
x = 0, *x
 
# 状態リストを作成
m = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
m[0][0][0] = 1
 
for i in range(1,N+1):
    
    for k in range(S+1):

        # x を含めない
        m[i][k][0] += m[i-1][k][0] # まだ開始しない
        m[i][k][1] += m[i-1][k][0] + m[i-1][k][1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
        m[i][k][2] += m[i-1][k][0] + m[i-1][k][1] + m[i-1][k][2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

        # x を含める場合
        if k - x[i] >= 0:
            m[i][k][1] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
            m[i][k][2] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
        
        m[i][k][0] = m[i][k][0] % 998244353
        m[i][k][1] = m[i][k][1] % 998244353
        m[i][k][2] = m[i][k][2] % 998244353
            
print(m[N][S][2])

Submission status: Runtime Error

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

# 状態リストを作成
m = [[[0 for _ in range(3)] for _ in range(S+1)] for _ in range(N+1)]
m[0][0][0] = 1

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

        # x を含めない
        m[i][k][0] += m[i-1][k][0]  # まだ開始しない
        m[i][k][1] += m[i-1][k][0] + m[i-1][k][1]  # 今回から開始して加えない、もしくは既に開始しているが、加えない
        m[i][k][2] += m[i-1][k][0] + m[i-1][k][1] + m[i-1][k][2]  # 今回、開始・終了して加えない、今回開始して加えず終了。

        # x を含める場合
        if k - x[i] >= 0:
            m[i][k][1] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
            m[i][k][2] += m[i-1][k - x[i]][0] + m[i-1][k - x[i]][1]
            
print(m[N][S][2])

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

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 - 1][s - a] * (n - i + 1)) % MOD
print(ans)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


def solve(nums, s):
    @lru_cache(None)
    def dfs(i, k):
        if k < 0:
            return []
        if k == 0:
            return [i-1]
        if i >= n:
            return []
        if k == s:
            return dfs(i+1, k-nums[i])
        return dfs(i+1, k-nums[i]) + dfs(i+1, k)

    ans = 0
    n = len(nums)
    for i in range(n):
        for e in dfs(i, s):
            ans = (ans + (i+1)*(n-e)) % 998244353
    return ans


def main():
    n, s = map(int, input().split())
    nums = [int(c) for c in input().split()]
    print(solve(nums, s))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
GI = lambda: int(input()); GIS = lambda: map(int, input().split()); LGIS = lambda: list(GIS())

def count_unique_pairs(n):
    return n * (n - 1) // 2

def main():
    GI()
    arr = LGIS()

    d = {}
    for x in arr:
        d[x] = d.get(x, 0) + 1

    tot = sum(count_unique_pairs(v) for v in d.values())
    
    for x in arr:
        print(tot - count_unique_pairs(d[x]) + count_unique_pairs(d[x]-1))

def main():
    GI()
    arr = LGIS()

    d = {}
    for x in arr:
        d[x] = d.get(x, 0) + 1

    tot = sum(count_unique_pairs(v) for v in d.values())
    
    for x in arr:
        print(tot - d[x] + 1)

main()

Submission status: Runtime Error

Solution code:
import sys

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 = [0] * (S+1)
answer = 0
for a in A:
    dp[0] += 1 # Lの数は１個ずつ加わる
    prev = dp.copy()
    for i in range(S-a+1):
        dp[i+a] += prev[i]
    answer += dp[-1] # その位置をRとした時

print(answer % MOD)
# 26

Submission status: Runtime Error

Solution code:
import sys

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[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]; one = dp[i][j][1]; two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one
        dp[i+1][j][1] %= MOD; dp[i+1][j][2] %= MOD
        dp[i+1][j+a][1] %= MOD; dp[i+1][j+a][2] %= MOD

answer = dp[N][S][2] % MOD
print(answer)
# 11

Submission status: Runtime Error

Solution code:
import numpy as np

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

dp = np.zeros((N, S + 1), dtype=np.int64)
for i, a in enumerate(A):
    dp[i, a] = i + 1
    for s in range(a + 1, S + 1):
        dp[i, s] = dp[:i, s - a].sum() % M

ans = 0
for i in range(N):
    ans += (N - i) * dp[i, S]
    ans = ans % M
print(ans)

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
m=998244353
def f(a1,s1,x):
  l=len(a1)
  y=x
  if y==0:
    y=n-l+1
  if a1[0]==s1:
    if l==1:
      return y*l%m
    else:
      return (y*l+f(a1[1:],s1,x))%m
  elif l==1:
    return 0
  elif a1[0]>s1:
    return f(a1[1:],s1,x)
  else:
    return (f(a1[1:],s1,x)+f(a1[1:],s1-a1[0],y))%m
print(f(a,s,0))

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

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

print(int(res))

Submission status: Runtime Error

Solution code:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author silviase
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FKnapsackForAllSegments solver = new FKnapsackForAllSegments();
        solver.solve(1, in, out);
        out.close();
    }

    static class FKnapsackForAllSegments {
        public void solve(int testNumber, Scanner in, PrintWriter out) {

            int n = in.nextInt();
            int s = in.nextInt();
            int[] a = new int[n];

            ModInt[][] dp = new ModInt[n][3001];
            ModInt ans = new ModInt(0);
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
            }

            for (int i = 0; i <= s; i++) {
                dp[0][i] = new ModInt(0);
            }
            dp[0][a[0]] = new ModInt(1);
            for (int i = 1; i < n; i++) {
                for (int j = 1; j <= s; j++) {
                    if (j < a[i]) {
                        dp[i][j] = dp[i - 1][j];
                    } else if (j == a[i]) {
                        dp[i][j] = dp[i - 1][j].add(i + 1);
                    } else {
                        dp[i][j] = dp[i - 1][j].add(dp[i - 1][j - a[i]]);
                    }
                }
                ans = ans.add(dp[i][s]);
            }

            out.println(ans.getVal());

        }

    }

    static class ModInt {
        long val;
        int MOD = 998244353;

        public ModInt(long i) {
            this.val = (int) ((i + MOD) % MOD);
        }

        public ModInt add(long l) {
            return new ModInt(this.val + l);
        }

        public ModInt add(ModInt m) {
            return new ModInt(this.val + m.getVal());
        }

        public long getVal() {
            return val;
        }

    }
}

Submission status: Runtime Error

Solution code:
from sys import stdin
mod = 998244353
def solveAsPolynomial():
    from numpy import *
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    ans = 0
    f = np.zeros(S+1,int64)#f[k] := ある多項式のx**kの係数
    for A in a:
        #f = (f+1)(1+x**A)として更新していく
        f[0] += 1#f+1
        f[A:] += f[:-A].copy()#f*(1+x**A)
        f %= mod
        ans += f[S]
        #x**S = X**(A_1+...+A_k)ゆえ、f[S]は知りたい組み合わせの数と等しい
        ans %= mod
    return ans
def main():
  ans = solveAsPolynomial()
  print(ans)
if __name__ =="__main__":
  main()

Submission status: Runtime Error

Solution code:
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * (S + 1), 2)
mm = (1 << K * (S + 1)) - 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: Runtime Error

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 998244353

def solve():
    n,s = LI()
    a = LI()
    ans = 0
    dp = [0]*(s+1)
    for i in range(n):
        ai = a[i]
        for j in range(s+1)[::-1]:
            nj = j+ai
            if nj > s:
                continue
            dp[nj] += dp[j]
            dp[nj] %= mod
        dp[ai] += i+1
        dp[ai] %= mod
        ans += dp[s]
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 998244353

n, s = map(int, input().split())
a = [int(item) for item in input().split()]

dp = [[0] * (s+1) for _ in range(n)]
dp[0][0] = 1
if a[0] <= s:
    dp[0][a[0]] = 1
ans = 0
for i, item in enumerate(a[1:]):
    for j in range(s+1):
        # Not use item
        dp[i+1][j] += dp[i][j]
        dp[i+1][j] %= MOD
        # Do use item
        if j + item <= s:
            dp[i+1][j + item] += dp[i][j]
            dp[i+1][j + item] %= MOD
    # Start from i
    dp[i+1][item] += 1
    dp[i+1][0] += 1
    ans += dp[i+1][s]

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:
N,S = map(int,input().split())
 
A = list(map(int,input().split()))

N,S = inputIL()
A = inputIL()

dp = [0] * (S+1)
ans = 0
mod = 998244353


for i in range(N):
 
    ndp = []
    for ll in dp:
        ndp.append(ll)
 
    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod
 
    for j in range(S):
        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod
 
    ans += ndp[S]
    ans %= mod
 
    dp = ndp

print(ans)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]


mod = 998244353
inf = 1e10

#solve
def solve():
    n, s = LI()
    a = LI()
    dp1 = [0] * (s + 1)
    dp2 = [0] * (s + 1)
    ans = 0

    for i in range(n):
        for j in range(s + 1):
            dp2[j] = dp1[j]
        
        for j in range(a[i], s + 1):
            dp2[j] += dp1[j - a[i]]
            dp2[j] %= mod
        dp2[a[i]] += i + 1 
        ans += dp2[s]
        ans %= mod
        dp1 = dp2[::1]
        # print(dp2)
    print(ans)
            
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(s+1)]
dp[0] = 1
ans = 0
for i in range(n):
	for j in range(s, a[i]-1, -1):
		dp[j] += dp[j-a[i]]
		dp[j] %= MOD
	dp[a[i]] += i
	dp[a[i]] %= MOD
	ans += dp[s]
	ans %= MOD
print(ans)

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=[[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):
    B[i+1][j]+=B[i][j]
    if 0<=j-a and j<s:
      B[i+1][j]+=B[i][j-a]
    if j==s:
      B[i+1][j]+=B[i][j-a]*(n-i)
    B[i+1][j]%=mod
print(B[n][s])

Submission status: Runtime Error

Solution code:
N, S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
MOD =   998244353
DP = [[0 for p in range(S+1)]for x in range(N)]
ans = N * (A[0]==S)
DP[0][A[0]] = 1
for n,a in enumerate(A):
    if n==0:continue
    #もらう
    for p in range(a):
        DP[n][p] = DP[n-1][p]
    for p in range(a,S+1):
        DP[n][p] = DP[n-1][p] + DP[n-1][p-a]
    #初期化
    DP[n][a] += n+1
    ans += (DP[n][S]*(N-n))% MOD
    DP[n][S] = 0
    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=998244353
a=list(map(int,input().split()))
ans=0
for i in range(n):
    if a[i]<=s:
        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:
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: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]


mod = 998244353
inf = 1e10

#solve
def solve():
    n, s = LI()
    a = LI()
    dp = [[0] * (s + 1) for i in range(n + 1)]
    dp[0][0] = 1
    ans = 0
    for i in range(1, n + 1):
        dpi = dp[i]
        dpi1 = dp[i - 1]
        for j in range(s - a[i-1] + 1):
            # print(j)
            dpi[j + a[i-1]] = (dpi1[j] + dpi1[j + a[i-1]]) % mod
        for j in range(a[i-1]):
            dpi[j] = dpi1[j]
        ans += dpi[-1]
        ans %= mod
    print(ans)
            
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

L = 0
R = 0
count = 0

while L < N:

    R = L+1
    wa = sum(A[L:R])

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

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

    L += 1

print(998244353%count)

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 998244353
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
N,S = m()

a = l()

dp = [0 for i in range(3000+1)]

dp[0] = 1
for i in range(N):
    if i == 0:
        dp[a[i]] += 1
    else:
        po = [0 for j in range(3000+1)]
        for j in range(1,3000+1):
            po[j] += dp[j]
        for j in range(S+1,a[i]+1,-1):
            po[j] += dp[j-a[i]] * (N-i)
        if S == a[i]:
            po[S] += 1
        for j in range(3000+1):
            dp[j] += po[j]
            dp[j] %= mod



print(dp[S])

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:
#DP頓挫乙

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

DP=[[[] for j in range(3001)] for i in range(N)]
DP[0][A[0]].append([0, 0])
for i in range(1, N):
  DP[i][A[i]].append([i, i])
  for j in range(3001):
    DP[i][j]+=DP[i-1][j]
  for j in range(A[i]+1, 3001):
    tmp=DP[i-1][j-A[i]]
    for k in range(tmp):
      DP[i][j].append([k[0], j])

Submission status: Runtime Error

Solution code:
import sys 
MOD = 10**9 +7
INF = 10**5

def main():
    n,s = map(int,input().split())
    a = list(map(int,input().split()))

    dp = [[0] * (s + 1) for _ in range(n + 1)]
    for i in range(n):
        num = a[i]
        for j in range(1,s + 1):
            dp[i + 1][j] = dp[i][j] + dp[i][j - a[i]]
    
    print(dp[-1][-1])
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
l=list(map(int,input().split()))
mod=998244353
dp=[[0 for i in range(s+1)] for i in range(n+1)]
dp[0][0]=1
dpi=[[0 for i in range(s+1)] for i in range(n+1)]
dpi[0][0]=1
for i,a in enumerate(l,1):
    for j in range(a):
        dp[i][j]=dp[i-1][j]
    for j in range(a,s+1):
        dp[i][j]=dp[i-1][j-a]+dp[i-1][j]%mod
for i,a in enumerate(l[::-1],1):
    for j in range(a):
        dpi[i][j]=dpi[i-1][j]
    for j in range(a,s+1):
        dpi[i][j]=dpi[i-1][j-a]+dpi[i-1][j]%mod      
st=[]
en=[]
for i in range(n+1):
    st.append(dp[i][-1])
    en.append(dpi[i][-1])
ans=0
t=dp[-1][-1]
for L in range(1,n+1):
    for R in range(L,n+1):
        ans+=abs(st[R]+en[n-L+1]-t)
        ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
M = 998244353

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

def calc(A_list):
	data_table = [0 for _ in range(S + 1)]
	data_table[0] = 1
	
	sum_list = [0] * N
	sum = 0
	for j in range(N - 1, -1, -1):
		a = A_list[j]
		sum += a
		sum_list[j] = a
	
	counts_rev = []
	
	for j, a in enumerate(A_list):
		for i in range(S, -1, -1):
			data = data_table[i]
			if data > 0:
				s = i + a
				if s <= S:
					data_table[s] = (data_table[s] + data) % M
		
		s = S - sum_list[j]
		if s > 0 and s <= S:
			counts_rev.append(data_table[s])
		else:
			counts_rev.append(0)
	
	return data_table, counts_rev

d1, c1 = calc(A_list)
d2, c2 = calc(list(reversed(A_list)))

c2.reverse()

total = 0

for l in range(N):
	for r in range(l + 1, N + 1):
#		print(d1[l], c2[r] if r < N else 0)
		total += d1[l] - (c2[r] if r < N else 0)

print(total % M)

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 r in range(N):
  for s in range(S):
    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])