Problem:


Score : 1000 points

Problem Statement

Consider the following game:

The game is played using a row of N squares and many stones.

First, a_i stones are put in Square i\ (1 \leq i \leq N).

A player can perform the following operation as many time as desired: "Select an integer i such that Square i contains exactly i stones. Remove all the stones from Square i, and add one stone to each of the i-1 squares from Square 1 to Square i-1."

The final score of the player is the total number of the stones remaining in the squares.

For a sequence a of length N, let f(a) be the minimum score that can be obtained when the game is played on a.

Find the sum of f(a) over all sequences a of length N where each element is between 0 and K (inclusive).
Since it can be extremely large, find the answer modulo 1000000007 (= 10^9+7).

Constraints

1 \leq N \leq 100

1 \leq K \leq N

Input

Input is given from Standard Input in the following format:

N K

Output

Print the sum of f(a) modulo 1000000007 (= 10^9+7).

Sample Input 1

2 2

Sample Output 1

10

There are nine sequences of length 2 where each element is between 0 and 2. For each of them, the value of f(a) and how to achieve it is as follows:

f(\{0,0\}): 0 (Nothing can be done)

f(\{0,1\}): 1 (Nothing can be done)

f(\{0,2\}): 0 (Select Square 2, then Square 1)

f(\{1,0\}): 0 (Select Square 1)

f(\{1,1\}): 1 (Select Square 1)

f(\{1,2\}): 0 (Select Square 1, Square 2, then Square 1)

f(\{2,0\}): 2 (Nothing can be done)

f(\{2,1\}): 3 (Nothing can be done)

f(\{2,2\}): 3 (Select Square 2)

Sample Input 2

20 17

Sample Output 2

983853488



Sample input:
2 2


Sample output:
10

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 1_000_000_007

@njit((i8, i8), cache=True)
def main(N, K):
    power = np.zeros(N + 10, np.int64)
    power[0] = 1
    for n in range(1, N + 10):
        power[n] = power[n - 1] * (K + 1) % MOD
    ret = K * (K + 1) // 2 * N * power[N - 1] % MOD

    dp = np.array([1], np.int64)
    dp[0] = 1
    for n in range(N, 0, -1):
        newdp = np.zeros(len(dp) * (n + 1) // n + 1, np.int64)
        for k in range(K + 1):
            for t in range(len(dp)):
                if k > n:
                    x = 0
                else:
                    x = (k + t) // n
                    ret -= x * dp[t] % MOD * power[n - 1] % MOD
                newdp[t + x] += dp[t]
        dp = newdp % MOD
    return ret % MOD

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

print(main(N, K))

Submission status: Accepted

Solution code:

"""

https://atcoder.jp/contests/cf17-final/tasks/cf17_final_g

1回の操作で捨てられる石は1個
いくつ捨てられるかを考えた方がいいだろう

大きい方から?→そんなことはない
小さいほうから?→そんなことはない
今i=aiを満たしている中で最小のものからやるべき？→これはそう

数え上げなので…？ → X回とれる盤面は何通りあるか(1)
または、あるindexより右をX回選択できるindexより右側の数列は何通りか(2) → 左は自由

(2)の方がやりやすそう(Nはでかいとする)
→ 右端は1通り (Nのみ)
→ 右から2番目は 1回選択が N-1,A / 2回選択が N-2,N
→ 右から3番目は 1回選択が N-2,(0回選択)

右から順番に見てく？
100*100→10000個しか取れない
毎回何の数字か全探索したとしても 100^3で間に合う
取れる個数は100log100

3300 * 100 * 100 = 3.3*10^7
間に合いそう
"""

N,K = map(int,input().split())
mod = 10**9+7
lis = [0] * 3300
lis[0] = 1

for i in range(N,0,-1):

    nlis = [0] * 3300
    
    for j in range(K+1):

        for last in range(3300):

            if i < j:
                nlis[last] += lis[last]
                nlis[last] %= mod
            elif (last+j)//i + last < 3300:
                nlis[last+(last+j)//i] += lis[last]
                nlis[last+(last+j)//i] %= mod
                

    lis = nlis
    #print (lis[:20])

ans = K * (K+1) // 2 * pow(K+1,N-1,mod) * N
#print (ans)

for i in range(3300):
    ans -= lis[i] * i
    ans %= mod
print (ans)

"""
#test

ans = 0
for i in range(100,0,-1):
    ans += (ans//i) + 1
print (ans)
"""