山东省第五届省赛 Hearthstone II

斯特林数stirling

• 第一类 stirling数 s(n, k)

n个人分成k组，组内再按特定顺序围圈

也就是分成了k组，组内就像是项链颜色一样，

1. ( {A, B}, {C, D} )
2. ( {B, A}, {C, D} )

属于一组

1. ({A}, {B, C, D})
2. ({A}, {B, D, C})

不属于一组

给定 $s(n,0)=0,s(1,1)=1$，有递归关系$s(n,k)=s(n-1,k-1) + (n-1) s(n-1,k)$

• 第二类 stirling数

S(n, k) 是把p元素集合划分到k个不可区分的盒子里且没有空盒的划分个数。

公式:

$$ S(n, n) = 1 (n >= 0) $$

$$ S(n, 0) = 0 (n >= 1) $$

$$ S(n,k)=k*S(n-1,k)+S(n-1,k-1),\text (1<=k<=n-1) $$

这样题目就好解决了。第五届省赛题目神经病。

因为每个桌子是不同的，所以还要利用乘法原理，$ans*m!$