Problem:


Balls and Boxes 10

  
BallsBoxesAny wayAt most one ballAt least one ball

  
DistinguishableDistinguishable123

  
IndistinguishableDistinguishable456

  
DistinguishableIndistinguishable789

  
IndistinguishableIndistinguishable101112

Problem

You have $n$ balls and $k$ boxes. You want to put these balls into the boxes.

Find the number of ways to put the balls under the following conditions:

  
Each ball is not distinguished from the other.

  
Each box is not distinguished from the other.

  
Each ball can go into only one box and no one remains outside of the boxes.

  
Each box can contain an arbitrary number of balls (including zero).

Note that you must print this count modulo $10^9+7$.

Input

$n$ $k$

The first line will contain two integers $n$ and $k$.

Output

Print the number of ways modulo $10^9+7$ in a line.

Constraints

  
$1 \le n \le 1000$

  
$1 \le k \le 1000$

Sample Input 1

5 3

Sample Output 1

5

Sample Input 2

10 5

Sample Output 2

30

Sample Input 3

100 100

Sample Output 3

190569292



Sample input:
5 3


Sample output:
5

Submission status: Accepted

Solution code:
class Twelvefold(): #n <= 1000程度
    def __init__(self, n, mod, build=True):
        self.mod = mod
        self.fct = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.fct[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.fct[i + 1] = self.fct[i] * (i + 1) % mod
        self.inv[n] = pow(self.fct[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod
        if build: self.build(n)

    def build(self, n):
        self.stl = [[0 for j in range(n + 1)] for i in range(n + 1)]
        self.bel = [[0 for j in range(n + 1)] for i in range(n + 1)]
        self.prt = [[0 for j in range(n + 1)] for i in range(n + 1)]
        self.stl[0][0] = 1
        self.bel[0][0] = 1
        for i in range(n):
            for j in range(n):
                self.stl[i + 1][j + 1] = self.stl[i][j] + (j + 1) * self.stl[i][j + 1]
                self.stl[i + 1][j + 1] %= self.mod
        for i in range(n):
            for j in range(n):
                self.bel[i + 1][j + 1] = self.bel[i + 1][j] + self.stl[i + 1][j + 1] % self.mod
                self.bel[i + 1][j + 1] %= self.mod
        for j in range(n + 1):
            self.prt[0][j] = 1
        for i in range(n):
            for j in range(n):
                if i - j >= 0:
                    self.prt[i + 1][j + 1] = self.prt[i + 1][j] + self.prt[i - j][j + 1]
                else:
                    self.prt[i + 1][j + 1] = self.prt[i + 1][j]
                self.prt[i + 1][j + 1] %= self.mod

    def solve(self, element, subset, equate_element=False, equate_subset=False, less_than_1=False, more_than_1=False):
        assert not less_than_1 or not more_than_1
        n = element
        k = subset
        a = equate_element
        b = equate_subset
        c = less_than_1
        d = more_than_1
        id = a * 3 + b * 6 + c + d * 2
        tw = [self.tw1, self.tw2, self.tw3, self.tw4, self.tw5, self.tw6, self.tw7, self.tw8, self.tw9, self.tw10, self.tw11, self.tw12]
        return tw[id](n, k)

    def tw1(self, n, k):
        return pow(k, n, self.mod)

    def tw2(self, n, k):
        if k - n < 0: return 0
        return self.fct[k] * self.inv[k - n] % self.mod

    def tw3(self, n, k):
        return self.stl[n][k] * self.fct[k] % self.mod

    def tw4(self, n, k):
        if k == 0: return 0
        return self.fct[n + k - 1] * self.inv[n] * self.inv[k - 1] % self.mod

    def tw5(self, n, k):
        if k - n < 0: return 0
        return self.fct[k] * self.inv[n] * self.inv[k - n] % self.mod

    def tw6(self, n, k):
        if n - k < 0 or k == 0: return 0
        return self.fct[n - 1] * self.inv[k - 1] * self.inv[n - k] % self.mod

    def tw7(self, n, k):
        return self.bel[n][k]

    def tw8(self, n, k):
        if k - n < 0: return 0
        return 1

    def tw9(self, n, k):
        return self.stl[n][k]

    def tw10(self, n, k):
        return self.prt[n][k]

    def tw11(self, n, k):
        if k - n < 0: return 0
        return 1

    def tw12(self, n, k):
        if n - k < 0: return 0
        return self.prt[n - k][k]

n, k = map(int, input().split())
t = Twelvefold(1000, 10**9 + 7, 1)
print(t.solve(n, k, 1, 1, 0, 0))

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()

    # 分割数：N個の数をK個に分ける方法
    # 分けたものは区別できないので、3を[1,2],[2,1]のように分けるのは合わせて1カウント
    # dp[i][j] = dp[i][j-i] + dp[i-1][j] jをi個に分割する数
    # 蟻本P66

    dp = [[0 for _ in range(n + 1)] for __ in range(m + 1)]
    dp[0][0] = 1

    for i in range(1, m + 1):
        for j in range(n + 1):
            if j - i >= 0:
                dp[i][j] = dp[i - 1][j] + dp[i][j - i]
            else:
                dp[i][j] = dp[i - 1][j]
            dp[i][j] %= MOD
    print(dp[m][n])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#Balls and Boxes 10
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,k = map(int,readline().split())
mod = 10**9+7
#分割数
def partition(n,r): #P(n,r)
    dp = [[0]*(r+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n+1):
        for j in range(1,r+1):
            if j-1 >= 0:
                dp[i][j] += dp[i][j-1]

            if i-j >= 0:
                dp[i][j] += dp[i-j][j]
            
            dp[i][j] %= mod
    
    return dp[n][r]

print(partition(n,k))

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10**9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n, k = LI()

    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(k + 1):
        dp[0][i] = 1

    for i in range(n):
        for j in range(k):
            if i - j >= 0:
                dp[i+1][j+1] = dp[i+1][j] + dp[i-j][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]
            dp[i+1][j+1] %= MOD

    print(dp[-1][-1])

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
N = N + K
mod = 10 ** 9 + 7
P = [[0] * (K + 1) for i in range(N + 1)]
for i in range(1, N + 1):
	P[i][1] = 1
for i in range(1, min(N, K) + 1):
	P[i][i] = 1
for n in range(1, N + 1):
	for k in range(2, min(n - 1, K) + 1):
		P[n][k] = (P[n - k][k] + P[n - 1][k - 1]) % mod
print(P[N][K])

Submission status: Accepted

Solution code:
def way10(ball, box):
    """ball: False / box: False / constraints: None
    ans = P(ball, box)  Pは分割数 / 計算量 O(ball * box)
    """
    # P[i][j] := 整数iを順序を区別せずに「j以下の自然数」の和に分ける場合の数
    P = [[0] * (ball + 1) for _ in range(ball + 1)]
    for j in range(ball + 1):
        P[0][j] = 1
    for i in range(ball):
        for j in range(ball):
            if i - j >= 0:
                P[i + 1][j + 1] = (P[i + 1][j] + P[i - j][j + 1]) % MOD
            else:
                P[i + 1][j + 1] = P[i + 1][j]
    return P[ball][min(box, ball)]


n, k = map(int, input().split())
MOD = 10 ** 9 + 7

print(way10(n, k))

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, K = iim()
    mod = 10**9 + 7

    if N == 1 or K == 1:
        print(1)
        return

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

    def ik(n, k):
        for i in range(1, min(k,n+1)):
            yield (i, i)
        for i in range(i+1, n+1):
            yield (i, k)

    for i, kx in ik(N, K):
        for k in range(1, kx+1):
            dp[i][k] = dp[i-1][k-1] + dp[i-k][k]

    #for row in dp:
    #    print(row)

    print(sum(dp[N]) % mod)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
sys.setrecursionlimit(500000)
mod = 10**9+7
@lru_cache(maxsize=None)
def partition(n, k):  # 自然数 n を k 個の自然数の和で表す場合の数
    if n < 0 or n < k:
        return 0
    elif k == 1 or n == k:
        return 1
    else:
        return (partition(n-k, k) + partition(n-1, k-1)) % mod  # 1 を使わない場合と使う場合の和
n, k = map(int, input().split())
print(partition(n+k, k))

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    modulo = 10 ** 9 + 7
    dp = [[0] * (n + 1)] * (k + 1)
    dp[0][0] = 1
    for i in range(1, k + 1):
        for j in range(n + 1):
            if i <= j:
                dp[i][j] = dp[i - 1][j] + dp[i][j - i]
            else:
                dp[i][j] = dp[i - 1][j]
    ans = dp[k][n] % modulo

    print(ans)

Submission status: Accepted

Solution code:
import math
def comb(n, k):
    if n < 0 or k < 0 or n < k: return 0
    return math.factorial(n) // math.factorial(n-k) // math.factorial(k)



n,k = map(int, input().split())
MOD = 10 ** 9 + 7

dp = [[0] * (n+1)] * (k+1)

dp[0][0] = 1
for i in range(1, k+1):
    for j in range(n+1):
        if j >= i: dp[i][j] = (dp[i-1][j] + dp[i][j-i])%MOD
        else: dp[i][j] = dp[i-1][j]

print(dp[k][n])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
MOD = 10**9 + 7
 
D = [[0]*(K+1) for i in range(N+1)]
for n in range(0, N+1):
    D[n][1] = 1
for k in range(1, K+1):
    D[0][k] = 1
for n in range(1, N+1):
    for k in range(1, K+1):
        if n >= k:
            D[n][k] = (D[n-k][k] + D[n][k-1]) % MOD
        else:
            D[n][k] = D[n][n]
print(D[N][K])

Submission status: Accepted

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

partition = {i: {j: 0 for j in range(k + 1)} for i in range(n + 1)}
for j in range(k+1):
    partition[0][j] = 1
for i in range(1, n+1):
    for j in range(1, k+1):
        if i - j >= 0:
            partition[i][j] = (partition[i][j - 1] + partition[i - j][j]) % MOD
        else:
            partition[i][j] = partition[i][j - 1] % MOD
ans = partition[n][k]
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
MOD = pow(10,9)+7
dp = [[0]*(n+1) for _ in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
    for j in range(n+1):
        if j-i >= 0:
            dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % MOD
        else:
            dp[i][j] = dp[i-1][j]
print(dp[k][n])

Submission status: Accepted

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

D = [[0]*(K+1) for i in range(N+1)]
for n in range(0, N+1):
    D[n][1] = 1
for k in range(1, K+1):
    D[0][k] = 1
for n in range(1, N+1):
    for k in range(1, K+1):
        if n >= k:
            D[n][k] = (D[n-k][k] + D[n][k-1]) % MOD
        else:
            D[n][k] = D[n][n]
print(D[N][K])