WIKI

斯特林数

斯特林数有两种

第一类斯特林数
$$ s(n,k) $$
将 $n$ 个 不同的元素 分配到 k 个圆排列中，圆不能为空
$$ s(n,k)=s(n-1,k-1)+(n-1)\times s(n-1,k),1\le k\le n\\ s(0,0)=1,s(k,0)=0,1\le k \le n $$
第二类斯特林数
$$ s(n,k) $$
将 $n$ 个 不同的元素 分配到 k 个相同的盒子中，盒子不能为空
$$ s(n,k)=ks(n-1,k)+ s(n-1,k-1),1\le k\le n\\ s(0,0)=1,s(k,0)=0,1\le k \le n $$
P1655 小朋友的球

小朋友最近特别喜欢球。有一天他脑子抽了，从口袋里拿出了 $N$ 个不同的球，想把它们放到 $M$ 个相同的盒子里，并且要求每个盒子中至少要有一个球，他好奇有几种放法，于是尝试编程实现，但由于他天天不好好学习，只会上 B 站看游泳教练，于是他向你求助。

think

是第二类斯特林数，但是涉及到高精度

所以我们用python实现

code

from functools import lru_cache

@lru_cache(None)
def S(n, m):
    if n == 0 and m == 0:
        return 1
    elif n == 0 or m == 0:
        return 0
    else:
        return m * S(n - 1, m) + S(n - 1, m - 1)

def solve():
    n, m = map(int, input().split())
    print(S(n, m))

if __name__ == "__main__":
    while True:
        try:
            solve()
        except EOFError:
            break