Problem:


Balls and Boxes 12

  
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 must contain at least one ball.

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

10 5

Sample Output 1

7

Sample Input 2

30 15

Sample Output 2

176

Sample Input 3

100 30

Sample Output 3

3910071



Sample input:
10 5


Sample output:
7

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, 1))

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 prepare(n, MOD):
    # 1! - n! の計算
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    # n!^-1 の計算
    inv = pow(f, MOD - 2, MOD)
    # n!^-1 - 1!^-1 の計算
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


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

    if n < m:
        print(0)
        exit()
    else:
        n -= m
    # 分割数：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:
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()

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

        for i in range(n - k):
            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])
    else:
        print(0)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
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 way12(ball, box):
    """ball: False / box: False / constraints: 1 or more
    ans = P(ball - box, box)  Pは分割数 / 計算量 O(ball * box)
    """
    if ball < box: 
        return 0
 
    # P[i][j] := 整数iを順序を区別せずに「j以下の自然数」の和に分ける場合の数
    diff = ball - box
    P = [[0] * (diff + 1) for _ in range(diff + 1)]
    for j in range(diff + 1):
        P[0][j] = 1
    for i in range(diff):
        for j in range(diff):
            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[diff][min(diff, box)]


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

print(way12(n, k))

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())
from itertools import chain, repeat

def resolve():
    N, K = iim()

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

    mod = 10**9 + 7

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

    for i, kx, i0 in zip( range(1, N+1), chain(range(1, K), repeat(K)), chain(repeat(1, N+1-K), range(2, K+1))):
        #print(i, kx, i0)
        for k in range(i0, kx + 1):
            dp[i][k] = dp[i-1][k-1] + dp[i-k][k]

    #for row in  dp:
    #    print(row)

    print(dp[N][K] % 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))

Submission status: Accepted

Solution code:
# (n - k, k) version of DPL_5_J.
if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    if n < k:
        print(0)
        exit(0)
    modulo = 10 ** 9 + 7
    dp = [[0] * (n + 1 - k)] * (k + 1)
    dp[0][0] = 1
    for i in range(1, k + 1):
        for j in range(n + 1 - k):
            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 - k] % 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]

if n >= k: print(dp[k][n-k])
else: print(0)

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 i in range(1, N+1):
    D[i][1] = 1
for i in range(1, min(N, K)+1):
    D[i][i] = 1
for n in range(1, N+1):
    for k in range(2, min(n-1, K)+1):
        D[n][k] = (D[n-k][k] + D[n-1][k-1]) % MOD
print(D[N][K] % MOD)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def partition_num(n, k, mod):
    partition = {i: defaultdict(int) for i in range(n + 1)}
    for j in range(1, k+1):
        partition[0][j] = 1
    for i in range(1, n+1):
        partition[i][1] = 1
        for j in range(2, 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
    return partition
if N-K >= 0:
    p = partition_num(N-K, K, MOD)
    ans = p[N-K][K]
else:
    ans = 0
print(ans)

Submission status: Accepted

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