Problem:


Balls and Boxes 9

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

4 3

Sample Output 1

6

Sample Input 2

10 5

Sample Output 2

42525

Sample Input 3

100 30

Sample Output 3

203169470



Sample input:
4 3


Sample output:
6

Submission status: Accepted

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

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

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

m_comb = {}
m_pow = {}
m_inv = {}

def comb(N, K):
    if (N, K) in m_comb:
        return m_comb[(N, K)]
    if N == K or K == 0:
        m_comb[(N, K)] = 1
        return 1
    m_comb[(N, K)] = (comb(N - 1, K) + comb(N - 1, K - 1)) % MOD
    return m_comb[(N, K)]

def pow(N):
    if N in m_pow:
        return m_pow[N]
    ret = 1
    for i in range(n):
        ret *= N
        ret %= MOD
    m_pow[N] = ret
    return ret

def inv(N):
    if N in m_inv:
        return m_inv[N]
    pow_num = MOD - 2
    pow_cur = N
    ret = 1
    while pow_num > 0:
        if pow_num % 2 == 1:
            ret *= pow_cur
            ret %= MOD
        pow_cur *= pow_cur
        pow_cur %= MOD
        pow_num /= 2
    m_inv[N] = ret
    return ret

ans = pow(k)
sig = -1

for i in range(k - 1, 0, -1):
    ans += (comb(k, i) * pow(i) % MOD) * sig
    sig *= -1

for i in range(1, k + 1):
    ans *= inv(i)
    ans %= MOD

print ans

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

Submission status: Accepted

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

if N<K:
    print(0)
    exit()

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

# nはn個のボールをいれるのを1から順番に考える
for n in range(1, N+1):
    D0 = D[n-1]
    # kはkこの箱にnこれいた場合の数
    for k in range(1, K+1):
        # 前回D[n-1][k-1]はk-1個の箱にn-1個入れてるので、それにn個めを新しい箱に入れるとD0[k-1]を足すことになる
        # 前回D[n-1][k-1]はk-1個の箱にn-1個入れてて、それぞれにn個めを1個足してくとそのパターンはk*D0[k]個ある
        # 頭ヨ
        D[n][k] = (D0[k-1] + k * D0[k]) % MOD
print(D[N][K] % MOD)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n,r = map(int,readline().split())
mod = 10**9+7

# 包除原理を用いたスターリング数
# AOJ Balls and Boxes 9で動作済み
def pow(n,p,mod=mod): #繰り返し二乗法(nのp乗)
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

def factrial_memo(n=10**5,mod=mod):
    fact = [1, 1]
    for i in range(2, n + 1):
        fact.append((fact[-1] * i) % mod)
    return fact

fact = factrial_memo()

def permutation(n,r): #nPr
    return fact[n]*pow(fact[n-r],mod-2)%mod
def combination(n,r): #nCr
    return permutation(n,r)*pow(fact[r],mod-2)%mod
    #return fact[n]*pow(fact[n-r],mod-2)*pow(fact[r],mod-2)
def homogeneous(n,r): #nHr
    return combination(n+r-1,r)%mod
    #return fact[n+m-1]*pow(fact[n-1],mod-2)*pow(fact[r],mod-2)

def stirling(n,r): #nSr
    res = 0
    for i in range(r): #包除原理で「箱区別あり」を求める
        res += pow(-1,i)*combination(r,i)*pow(r-i,n)
        res %= mod
    for i in range(1,r+1): #r!で除する
        res *= pow(i,mod-2)%mod
        res %= mod
    return res

print(stirling(n,r))

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)]
    dp[0][0] = 1

    for i in range(n):
        for j in range(k):
            dp[i+1][j+1] = dp[i][j] + (j + 1) * dp[i][j+1]
            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())
mod = 10 ** 9 + 7
S = [[0] * (K + 1) for i in range(N + 1)]
S[0][0] = 1
for n in range(1, N + 1):
	for k in range(1, K + 1):
		S[n][k] = (S[n - 1][k - 1] + k * S[n - 1][k]) % mod
print(S[N][K])

Submission status: Accepted

Solution code:
def way9(ball, box):
    """ball: True / box: False / constraints: 1 or more
    -> ans = S(ball, box)  Sはスターリング数 / 計算量 O(ball * box)
    """
    if ball < box:
        return 0

    # S[i][j] := i個(区別する)をkグループ(区別しない)に分ける場合の数
    S = [[0] * (box + 1) for i in range(ball + 1)] 
    S[0][0] = 1
    for i in range(ball):
        for j in range(box):
            S[i + 1][j + 1] = S[i][j] + S[i][j + 1] * (j + 1)
            S[i + 1][j + 1] %= MOD

    return S[ball][box]


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

print(way9(n, k))

Submission status: Accepted

Solution code:
mod = 10**9 + 7
stering = [[-1]*1001 for _ in range(1001)]
for i in range(1001):
    stering[i][1] = 1
    stering[i][i] = 1

def roop(n, k):
    if stering[n][k] != -1:
        return stering[n][k]
    else:
        stering[n][k] = (roop(n-1, k-1) + k * roop(n-1, k)) % mod
        return stering[n][k]

n, k = [int(s) for s in input().split()]
if n < k:
    print(0)
else:
    ans = roop(n, k)
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

mod = 10**9 + 7
star = [[None] * 1001 for _ in range(1001)]

for i in range(1001):
    star[i][i] = 1
    star[i][1] = 1

def search(n, k):
    if star[n][k]:
        return star[n][k] % mod
    else:
        star[n][k] = (search(n-1, k-1) + k * search(n-1, k)) % mod
        return star[n][k]

n, k = map(int, input().split())
if n < k:
    print(0)
else:
    print(search(n,k))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**4)

n, k = map(int, input().split())
stirling = [[-1 for _ in range(k+1)] for _ in range(n+1)]

MOD = 10**9 + 7

def rec(nn, kk):
    if nn < kk:
        return 0
    if kk == 1 or kk == nn:
        return 1
    if stirling[nn][kk] == -1:
        stirling[nn][kk] = (kk * rec(nn-1, kk) + rec(nn-1, kk-1)) % MOD
    return stirling[nn][kk]

print(rec(n, k))

Submission status: Accepted

Solution code:
#!python3

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

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

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

    dp0, dp1 = dp
    dp0[0] = 1
    for i in range(1, N+1):
        for j in range(1, K+1):
            dp1[j] = (dp0[j-1] + dp0[j]*j) % mod
        dp1[0] = 0
        dp0, dp1 = dp1, dp0
    print(dp0[K] % mod)
if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from functools import lru_cache
import sys

mod=1000000007

n,k=[int(i) for i in input().split(" ")]



facts=[1 for i in range(n+k+1)]

for i in range(1,n+k+1):
    facts[i]=i*facts[i-1]

if n<k:
    print(0)
    sys.exit()

tables=[[-1 for i in range(k+1)] for j in range(n+1)]

def f(n,k):
    if k==1:
        return 1

    elif n==k:
        return facts[n]

    elif tables[n][k]!=-1:
            return tables[n][k]

    else:
        retval=(k*f(n-1,k)+k*f(n-1,k-1))
        tables[n][k]=retval
        return retval

print((f(n,k)//facts[k])%mod)

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    # "n 要素を" は区別できる n 要素
    # "k グループ" はちょうど k グループ

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def C(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def P(self, n, r):
        if not 0 <= r <= n: return 0
        return self.fac[n] * self.facinv[n-r] % self.mod

    def H(self, n, r):
        if (n == 0 and r > 0) or r < 0: return 0
        return self.fac[n+r-1] * self.facinv[r] % self.mod * self.facinv[n-1] % self.mod

    def rising_factorial(self, n, r):  # 上昇階乗冪 n * (n+1) * ... * (n+r-1)
        return self.fac[n+r-1] * self.facinv[n-1] % self.mod

    def stirling_first(self, n, k):  # 第 1 種スターリング数  lru_cache を使うと O(nk)  # n 要素を k 個の巡回列に分割する場合の数
        if n == k: return 1
        if k == 0: return 0
        return (self.stirling_first(n-1, k-1) + (n-1)*self.stirling_first(n-1, k)) % self.mod

    def stirling_second(self, n, k):  # 第 2 種スターリング数 O(k + log(n))  # n 要素を区別のない k グループに分割する場合の数
        if n == k: return 1  # n==k==0 のときのため
        return self.facinv[k] * sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def balls_and_boxes_3(self, n, k):  # n 要素を区別のある k グループに分割する場合の数  O(k + log(n))
        return sum((-1)**(k-m) * self.C(k, m) * pow(m, n, self.mod) for m in range(1, k+1)) % self.mod

    def bernoulli(self, n):  # ベルヌーイ数  lru_cache を使うと O(n**2 * log(mod))
        if n == 0: return 1
        if n % 2 and n >= 3: return 0  # 高速化
        return (- pow(n+1, self.mod-2, self.mod) * sum(self.C(n+1, k) * self.bernoulli(k) % self.mod for k in range(n))) % self.mod

    def faulhaber(self, k, n):  # べき乗和 0^k + 1^k + ... + (n-1)^k
        # bernoulli に lru_cache を使うと O(k**2 * log(mod))  bernoulli が計算済みなら O(k * log(mod))
        return pow(k+1, self.mod-2, self.mod) * sum(self.C(k+1, j) * self.bernoulli(j) % self.mod * pow(n, k-j+1, self.mod) % self.mod for j in range(k+1)) % self.mod

    def lah(self, n, k):  # n 要素を k 個の空でない順序付き集合に分割する場合の数  O(1)
        return self.C(n-1, k-1) * self.fac[n] % self.mod * self.facinv[k] % self.mod

    def bell(self, n, k):  # n 要素を k グループ以下に分割する場合の数  O(k**2 + k*log(mod))
        return sum(self.stirling_second(n, j) for j in range(1, k+1)) % self.mod

mod = 10**9+7
comb = Combination(2000)
n, k = map(int, input().split())
print(comb.stirling_second(n, k))

Submission status: Accepted

Solution code:
import math


def combination(i: int, j: int) -> int:
    return math.factorial(i) // math.factorial(i - j) // math.factorial(j)


if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    modulo = 10 ** 9 + 7
    ans = 0
    if k <= n:
        for i in range(k):
            if 0 == i % 2:
                ans += (k - i) ** n * combination(k, i)
            else:
                ans -= (k - i) ** n * combination(k, i)
        ans = (ans // math.factorial(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

all = 0

for i in range(k):
    add = comb(k, i) * ((k-i) ** n)
    if i & 1: all = (all - add)
    else: all = (all + add)

print(all // (math.factorial(k)) % MOD)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

def Stirling_second(n, k, mod):
    Stir = {i: defaultdict(int) for i in range(n + 1)}
    Stir[1][1] = 1
    for i in range(2, n+1):
        Stir[i][1] = 1
        for j in range(2, k+1):
            Stir[i][j] = (Stir[i-1][j-1] + (j * Stir[i-1][j]) % mod) % mod
    return Stir
s = Stirling_second(N, K, MOD)
ans = s[N][K]
print(ans)

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split(" "))
if n<k:
    print(0)
else:
    a=[1,0]
    for i in range(n):
        a=[0]+[a[i-1]+i*a[i] for i in range(1,len(a))]+[0]
    print(a[k]%(10**9+7))