Problem:


Score : 100 points

Problem Statement

There are N children, numbered 1, 2, \ldots, N.

They have decided to share K candies among themselves.
Here, for each i (1 \leq i \leq N), Child i must receive between 0 and a_i candies (inclusive).
Also, no candies should be left over.

Find the number of ways for them to share candies, modulo 10^9 + 7.
Here, two ways are said to be different when there exists a child who receives a different number of candies.

Constraints

All values in input are integers.

1 \leq N \leq 100

0 \leq K \leq 10^5

0 \leq a_i \leq K

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 \ldots a_N

Output

Print the number of ways for the children to share candies, modulo 10^9 + 7.

Sample Input 1

3 4
1 2 3

Sample Output 1

5

There are five ways for the children to share candies, as follows:

(0, 1, 3)

(0, 2, 2)

(1, 0, 3)

(1, 1, 2)

(1, 2, 1)

Here, in each sequence, the i-th element represents the number of candies that Child i receives.

Sample Input 2

1 10
9

Sample Output 2

0

There may be no ways for the children to share candies.

Sample Input 3

2 0
0 0

Sample Output 3

1

There is one way for the children to share candies, as follows:

(0, 0)

Sample Input 4

4 100000
100000 100000 100000 100000

Sample Output 4

665683269

Be sure to print the answer modulo 10^9 + 7.



Sample input:
3 4
1 2 3


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,K = map(int, input().split())
# *A = map(int, input().split())
A = list(map(int, input().split()))
dp = [ [0]*(K+1) for _ in range(N+1)]

dp[0][K]= 1
MOD= int(1e9+7)

for i in range(N): # i+1$B$K(B
    for k in range(K, -1, -1):

        for ai in range(A[i]+1): # ai = 0 to Ai
            if k - ai >= 0:
                dp[i+1][k-ai] += dp[i][k] % MOD
            # print("dp[{ip1}][{kai}] += dp[{i}][{k}]".format(ip1=i+1, kai=k-ai, i=i, k=k))
# print(dp[N][K])
print(dp[N][0] % MOD)
# print(dp)

Submission status: Time Limit Exceeded

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

"""
参考：https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
・数え上げDP
・累積和で高速化
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
if sys.version_info.minor >= 5: from math import gcd
else: from fractions import gcd 
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, K = MAP()
aN = LIST()

# dp[この子までの範囲で][飴を配る総数] = 場合の数
dp = [[0] * (K*2+1) for i in range(N+1)]
dp[0][0] = 1

for i in range(N):
    sm = [0] * (K+2)
    # 今回送るi行について累積和を取る
    for j in range(1, K+2):
        sm[j] = sm[j-1] + dp[i][j-1]
    for j in range(K+1):
        # iが送る予定の長さに応じた区間和を取る
        dp[i+1][j] = sm[j+1] - sm[max(j-aN[i], 0)]
        # for k in range(aN[i]+1):
        #     dp[i+1][j+k] += dp[i][j]
print(dp[N][K] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=[now%mod for now in NOWSUM]
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]-=NOWSUM[j-a-1]


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数

def funct(a,b):
    return (a+b)%mod

for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW,funct))
    NEXT=copy.copy(NOWSUM)
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]-=NOWSUM[j-a-1]


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import copy

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=copy.copy(NOWSUM)
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]=(NEXT[j]-NOWSUM[j-a-1])%mod


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=[now%mod for now in NOWSUM]
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]-=NOWSUM[j-a-1]%mod


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=[NOWSUM[i]%mod  if i<=a else 0 for i in range(K+1)]
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]=(NOWSUM[j]-NOWSUM[j-a-1])%mod


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
    NEXT=[NOWSUM[i]  if i<=a else 0 for i in range(K+1)]
    #print(NEXT)

    for j in range(a+1,K+1):
        NEXT[j]=(NOWSUM[j]-NOWSUM[j-a-1])%mod


    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K]%mod)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))

    for j in range(K+1):
        if j-a-1>=0:
            NEXT[j]=(NOWSUM[j]-NOWSUM[j-a-1])%mod
        else:
            NEXT[j]=NOWSUM[j]%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for a in A:
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NOWSUM[j+1]-NOWSUM[max(0,j-a)])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])

Submission status: Time Limit Exceeded

Solution code:
import itertools

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=list(itertools.accumulate(NOW))
        
    for j in range(K+1):
        if j-A[i]-1>=0:
            NEXT[j]=(NEXT[j]+NOWSUM[j]-NOWSUM[j-A[i]-1])%mod
        else:
            NEXT[j]=(NEXT[j]+NOWSUM[j])%mod
            

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW=[0]*(K+1)
NOW[0]=1#そこまでi個使ったときの場合の数


for i in range(N):
    NEXT=[0]*(K+1)
    NOWSUM=[0]
    for n in NOW:
        NOWSUM.append(NOWSUM[-1]+n)
        
    for j in range(K+1):
        NEXT[j]=(NEXT[j]+NOWSUM[j+1]-NOWSUM[max(0,j-A[i])])%mod

    NOW=NEXT
    #print(NOWSUM,NOW)

print(NOW[K])

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
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 [int(x) for x in sys.stdin.readline().split()]
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 main():
    n,k = LI()
    a = LI()

    t = [[0]*(k+1) for _ in range(n)]
    z = t[-1]
    for i in range(a[-1]+1):
        z[i] = 1

    for i in range(n-2,-1,-1):
        s = 0
        z = t[i]
        y = t[i+1]
        c = a[i] + 1
        for j in range(c):
            s += y[j]
            s %= mod
            z[j] = s

        for j in range(c,k+1):
            s += y[j] - y[j-c]
            s %= mod
            z[j] = s

    return t[0][-1]


print(main())

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = list(map(int,input().split()))
c = []
c_re = [0]
tmp = 0
for e in a:
    tmp += e
    c.append(tmp)
tmp = 0
for e in reversed(a):
    tmp += e
    c_re.append(tmp)
c_re = list(reversed(c_re))
# sum(a) < K ならば0通り
# dp[i][j]:i番目までの子供,残っている飴の個数j ans = dp[N][0]
# 0 <= k <= min(c[i] ,K) - j
# dp[i][j] += dp[i-1][j+k]
dp = [[0]*(K+1) for i in range(N+1)]
dp[0][K] = 1
for i in range(1,N+1):
    inf = K - c[i-1] if K - c[i-1] > 0 else 0
    for j in range(inf,min(c_re[i],K) + 1):
        for k in range(min(a[i-1],K-j) + 1): 
            dp[i][j] += dp[i-1][j+k]
ans = dp[N][0] % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
dp = [[0 for _ in [0]*(k+1)] for _ in [0]*n]
sum_list = [[0] for _ in [0]*n]

def make_sum(i):
	for j in range(k+1):
		sum_list[i].append(sum_list[i][-1] + dp[i][j])
	return

for j in range(a[0]+1):
	dp[0][j] = 1

for i in range(1, n):
	make_sum(i-1)
	for j in range(k+1):
		dp[i][j] = sum_list[i-1][j+1] - sum_list[i-1][max(0, j-a[i])]

print(dp[n-1][k] % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N,K=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7

NOW={0:1}#そこまでの飴の個数,場合の数

for i in range(N):
    NEXT=defaultdict(int)
    for now in NOW:
        for j in range(A[i]+1):
            if now+j<=K:
                NEXT[now+j]=(NEXT[now+j]+NOW[now])%mod

    NOW=NEXT
    #print(NOW)

print(NOW[K])

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
C = 10**9+7

dp = [[0]*(K+1) for _ in range(N)]
dp[0] = [1]*(A[0]+1)+[0]*(K-A[0])
csum = [[0]*(K+2) for _ in range(N)]

# l=max(0,j[A[i]])のとき
# dp[i][j]=sum(dp[i][l,j+1])としたいがO(NK**2)で間に合わない
# ->和を取る操作を高速化するために累積和のテーブルを準備する

for i in range(1, N):
    for j in range(K+1):
        csum[i-1][j+1] = (csum[i-1][j]+dp[i-1][j]) % C
        l = max(0, j-A[i])
        dp[i][j] = (csum[i-1][j+1]-csum[i-1][l]) % C
print(dp[-1][-1])

Submission status: Accepted

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

# dp[i][j] = i番目の子供まででj個の飴を配る場合の数
# dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + ... + dp[i - 1][j - A[i]]
# 累積和を使える

N,K = map(int,readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

dp = [[0] * (K + 1) for i in range(N + 1)]
dp[0][0] = 1
sdp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(len(sdp[0])):
  sdp[0][i] = 1

for i in range(1, N + 1):
  for j in range(K + 1):
    # dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + ... + dp[i - 1][j - A[i]]
    # 左端をj - A[i], 右端をjとする累積和
    dp[i][j] = sdp[i - 1][j]
    if j - A[i - 1] - 1 >= 0:
      dp[i][j] -= sdp[i - 1][j - A[i - 1] - 1]
    dp[i][j] %= DIV
  sdp[i][0] = dp[i][0]
  for j in range(1, K + 1):
    sdp[i][j] = sdp[i][j - 1] + dp[i][j]
    sdp[i][j] %= DIV

print(dp[N][K])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

#import
#import math
#import numpy as np
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10 ** 9 + 7

def mod(num):
    return num % MOD

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

for i in range(1, N + 1):
    s = [0] * (K + 2)
    for j in range(1, K + 2):
        s[j] = mod(s[j - 1] + dp[i - 1][j - 1])

    for j in range(K + 1):
        dp[i][j] =  mod(s[j + 1] - s[max(0, j - A[i-1])])

print(dp[N][K])

Submission status: Accepted

Solution code:
from itertools import accumulate

N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
DP = [0] * (K+2)
DP[0] = 1
for a in A:
    D = [0] * (K+2)
    for i, d in enumerate(DP):
        if d > 0:
            D[i] += d
            D[min(K+1, i + a + 1)] -= d
    for i in range(1, K+2):
        D[i] += D[i-1]
        D[i] %= mod
    DP = D
print(DP[K])

Submission status: Accepted

Solution code:
mod = 1000000007
n, k = map(int, input().strip().split())
arr = list(map(int, input().strip().split()))

dp = [[0 for i in range(n+1)] for i in range(k+2)]

for i in range(1, k+2):
    dp[i][0] = 1

for i in range(1, k+2):
    for j in range(1, n+1):
        K = i-1
        if K < arr[j-1]:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]-dp[0][j-1]
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-arr[j-1]-1][j-1]
        
        dp[i][j] %= mod


print((dp[-1][-1]-dp[-2][-1] + mod)%mod)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

def main():
  input=sys.stdin.readline
  n,k=map(int,input().split())
  A=list(map(int,input().split()))
  mod=10**9+7
  dp=[0]*(k+1)
  dp[0]=1
  for a in A:
    dp=list(accumulate(dp))
    #print("accumulated",dp)
    for j,d in enumerate(dp[:k-a],start=a+1):
      dp[j]-=d
    dp=[dpi%mod for dpi in dp]
    #print(dp)
  print(dp[k])
"""
def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  for i in range(0,n+1):
    for j in range(0,k+1):
      if i==0 and j==0:
        dp[i][j]=1
        break
      if j==0:
        dp[i][j]=1
        continue
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k])"""
main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
mod=10**9+7
dp=[[0]*(k+1) for _ in range(n+1)]
dp[0][0]=1
for i in range(1,n+1):
    accum=[0,dp[i-1][0]]
    for j in range(1,k+1):
        accum.append((dp[i-1][j]+accum[-1])%mod)
    for j in range(k+1):
        dp[i][j]+=(accum[j+1]-accum[max(j-a[i-1],0)]+mod)%mod
        dp[i][j]%=mod
print(dp[n][k])

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")


# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


from collections import defaultdict, deque


class Graph(object):
    def __init__(self, dic):
        self.dict = dic
        self.vertex = set()

    def addedge(self, a, b):
        if self.dict[a] == []:
            self.vertex.add(a)
        if b != None:
            self.dict[a].append(b)

    def con_com_util(self, i, unvisited, count, comp):
        for j in self.dict[i]:
            if j in unvisited:
                unvisited.remove(j)
                comp[count].append(j)
                comp = self.con_com_util(j, unvisited, count, comp)
        return comp

    def conn_components(self):
        unvisited = self.vertex.copy()
        count = 0
        comp = defaultdict(list)
        while unvisited:
            i = unvisited.pop()
            comp[count].append(i)
            comp = self.con_com_util(i, unvisited, count, comp)
            count += 1
        return (count, comp)


def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



from sys import setrecursionlimit
setrecursionlimit(1000000)
N=10**9 + 7
n,k=sep()
ar=lis()
dp=[[0 for _ in range(k+5)] for _ in range(n+5)]
prev=[0]*(k+5)
for j in range(min(ar[0]+1,k+1)):
    dp[1][j]=1
prev[0]=1
for j in range(1,k+1):
    prev[j] = (prev[j - 1] + dp[1][j]) % N
for i in range(2,n+1):
    for j in range(0,k+1):
        if j-ar[i-1]>0:
            dp[i][j]=((dp[i][j]+prev[j]-prev[j-ar[i-1]-1])%N +N)%N
        else:
            dp[i][j]=(dp[i][j]+prev[j])%N
    prev[0]=dp[i][0]
    for j in range(1,k+1):
        prev[j]=(prev[j-1]+dp[i][j])%N





print(dp[n][k])

Submission status: Accepted

Solution code:
'''
問題を言い換えると
0<=bi<=ai for any iにおいて、sum_i bi = Kとなる通りの数を求めよ

dp[i,j] .. 通りの総数、総和がちょうどjになるとき、:iまでの子供を考慮したとき
dp[i+1,j]=sum_{k=0}^{a_{i}} dp[i,j-k]

これではTLEになりそうなので、累積和で高速に計算する必要がある
'''

import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  # 文字列読み込む時はこっち

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(readline())


def ints(): return np.fromstring(readline(), sep=' ', dtype=np.int64)


MOD = 10**9 + 7

N, K = ints()
A = ints()

from numba import njit


@njit('(i8,i8,i8[:])', cache=True)
def solve(N, K, A):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(N):
        # 前の列の累積和を作りたい
        total = 0
        for j in range(K + 1):
            # ai個でところてんすればいい
            total += dp[i, j]
            total %= MOD
            if j - A[i] - 1 >= 0:
                total -= dp[i, j - A[i] - 1]
            dp[i + 1, j] = total % MOD

    print(dp[N, K])


solve(N, K, A)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = [0] + list(map(int, input().split()))
DP = [[0 for k in range(K+1)] for n in range(N+1)]
cs = [[0 for k in range(K+2)] for n in range(N+1)]
for i in range(1,N+1):
    for j in range(0,K+2):
        if i == 1 and j <= K:
            if j <= a[i]:
                DP[i][j] = 1
            else:
                DP[i][j] = 0
        elif j <= K:
            DP[i][j] += (cs[i-1][j+1] - cs[i-1][max(j-a[i],0)])%(10**9+7)
        if j > 0:
            cs[i][j] = (cs[i][j-1]%(10**9+7) + DP[i][j-1]%(10**9+7))%(10**9+7)
print(DP[N][K])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
dp = [[0]*(K+1) for i in range(N+1)]

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

for i in range(1, N+1):
    v = a[i-1]
    dp[i][0] += dp[i-1][0]
    dp[i][0] %= mod
    for j in range(1,K+1):
        if j-1-v >= 0:
            dp[i][j] += (dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1-v]) % mod
        else:
            dp[i][j] += (dp[i][j-1] + dp[i-1][j]) % mod
if K>0:            
    ans = (dp[N][K] - dp[N][K-1]) % mod
else:
    ans = dp[N][K] % mod
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

N, K = map(int, input().split())

max_candies = np.array(list(map(int, input().split())), dtype='int64')

dpt = np.full((N+1, K+1), 0, dtype='int64')
for i in range(K+1):
    dpt[0][i] = 1

@njit('i8(i8,i8,i8[:],i8[:,:])', cache=True)
def dp(N, K, max_candies, dpt):
    for i in range(1, N+1):
        for j in range(0, K+1):
            dpt[i][j] += dpt[i-1][j]
            t = j - max_candies[i-1] - 1
            if t >= 0:
                dpt[i][j] -= dpt[i-1][t]
            if j > 0:
                dpt[i][j] += dpt[i][j-1]
            dpt[i][j] = dpt[i][j] % (10**9+7)
    return (dpt[N][K] - dpt[N][K-1]) % (10**9+7)

if K > 0:
    print(dp(N, K, max_candies, dpt))
else:
    print(1)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

N, K = map(int, input().split())

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

dpt = np.full((N+1, K+1), 0, dtype='int64')
for i in range(K+1):
    dpt[0][i] = 1

@njit
def dp(N, K, max_candies, dpt):
    for i in range(1, N+1):
        for j in range(0, K+1):
            dpt[i][j] += dpt[i-1][j]
            t = j - max_candies[i-1] - 1
            if t >= 0:
                dpt[i][j] -= dpt[i-1][t]
            if j > 0:
                dpt[i][j] += dpt[i][j-1]
            dpt[i][j] = dpt[i][j] % (10**9+7)
    return (dpt[N][K] - dpt[N][K-1]) % (10**9+7)

if K > 0:
    print(dp(N, K, max_candies, dpt))
else:
    print(1)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

N,K=map(int,input().split())
a=np.array([int(i) for i in input().split()],dtype=np.int64)

dp=np.full((N+1,K+1),0,dtype=np.int64)
c=np.full(K+2,0,dtype=np.int64)
MOD=10**9+7

@njit('i8(i8,i8,i8,i8[:,:],i8[:])', cache=True)
def main(N,K,MOD,dp,c):

    dp[0][0]=1
    for i in range(1,N+1):
        c[0]=0
        for j in range(1,K+2):
            c[j]=(c[j-1]+dp[i-1][j-1])%MOD
        for j in range(K+1):
            dp[i][j]=(c[j+1]-c[max(0,j-a[i-1])])%MOD

    return dp[N][K]

print(main(N,K,MOD,dp,c))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

f = [0] * (k + 1)
f[0] = 1
for i in range(n):
    for j in range(1, k+1):
        f[j] = (f[j] + f[j - 1]) % mod # 1/(1-x):累積和
    for j in range(k, a[i], -1): # 1-x^(a[i]+1) a[i]+1次したの項を引く
        f[j] = (f[j] - f[j - a[i] - 1]) % mod
print(f[-1])

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    dp[i + 1][0] = dp[i][0]
    for j in range(1, k+1):
        dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % mod
    for j in range(k, a[i], -1):
        dp[i + 1][j] = (dp[i + 1][j] - dp[i + 1][j - a[i] - 1]) % mod
print(dp[n][-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,k=MI()
lis=LI()
dp=[[0]*(k+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    sm=0
    for j in range(lis[i]+1):
        sm+=dp[i][j]
        dp[i+1][j]=sm%mod
    for j in range(lis[i]+1,k+1):
        sm+=dp[i][j]
        sm-=dp[i][j-lis[i]-1]
        dp[i+1][j]=sm%mod
print(dp[-1][-1]%mod)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
if n ==1: print(0 if k> A[0] else 1);exit()
dp = [[0]*(k+1) for _ in range(n)]
for i in range(A[0]+1):
    dp[0][i] = 1
for i in range(1,n):
    B = [0]
    for j in range(k+1):
        B.append(B[-1] + dp[i-1][j])
        B[-1]%=mod
    for j in range(k+1):
        dp[i][j] += B[j+1]-B[max(0,j-A[i])]
        dp[i][j] %= mod
print(dp[-1][-1]%mod)

Submission status: Accepted

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

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

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

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

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

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

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
def ACC1(l):
  N = len(l)
  ret = [0]*(N+1)
  for i in range(N):
    ret[i+1] = ret[i]+l[i]
  return ret
N,K = IL()
A = IL()

res = [0 for j in range(K+1)]
res[K] = 1

for i in range(N):
  acc = ACC1(res)
  for k in range(K):
    res[k] = acc[min(k+A[i],K)+1]-acc[k]
    res[k] %= MOD
print(res[0])