做题记录 十二重计数法

· · 个人记录

I

显然 m^n。

II

让每个球去选盒子，显然为 \mathcal{A}_m^n。

III

与第二类斯特林数有关

式子为 {n \brace m} m!。

但是，第二类斯特林数的递推式子是 O(nm) 的，因此我们需要一些优化。

法一：容斥

考虑总数为 m^n 然后考虑排除不合法的方案数。

我们可以固定一些盒子，让他们强制为空。

根据容斥的公式，那么不合法的，也就是有空盒的方案数即为

\sum_{k=1}^{m} (-1)^{k-1} {m\choose k}(m-k)^n

那么，我们可以得到，原问题的方案数可以不用第二类斯特林数，可以用容斥得到。

m^n-\sum_{k=1}^{m} (-1)^{k-1} {m\choose k}(m-k)^n =\sum_{k=0}^{m}(-1)^{k} {m\choose k}(m-k)^n

完事

法二：

考虑总的方案数为枚举哪些盒子为非空

m^n= \sum_{k=0}^m{n \choose k}{n \brace k}k!

直接二项式反演

{n \brace m}m!=\sum_{k=0}^{m}(-1)^{k} {m\choose k}(m-k)^n

IV

枚举有多少盒子非空。

\sum_{i=1}^{m} {n\brace i}

V

搞笑的，[n\le m]。

VI

第二类斯特林数的定义

可通过 III 得到。

VII

隔板，n+m-1\choose m-1。

VIII

考虑选出哪些盒子装球，m\choose n

IX

隔板 n-1\choose m-1。

X

考虑 dp，设 f_{i,j} 表示 i 个球，j 个盒子的方案数。

考虑新增一个盒子的方案数。

如果必须有空盒，那就加上一个空盒；不能有空盒，那就把已有的全部 +1.

但是，这是 $O(nm)$ 的。 所以，我们要上多项式优化。 构造多项式 $F_i(x)=(f_{i,0}+f_{i,1}x+f_{i,2}x^2+f_{i,3}x^3+...)

根据转移方程，则有

F_i(x)=F_{i-1}(x)\times (1+x^i+x^{2i}+...)

又根据生成函数

有 F_i(x)=\frac{F_{i-1}(x)}{1-x^i}

即

F_i(x)=\prod_{j=1}^i\frac{1}{1-x^j}

然后对这个东西取 ln，加回去再取 exp 即可。

详见付公主的背包 (不会，暂时贺上)

XI

搞笑的，[n\le m]

XII

先令每个盒子里有一个，转化成了 X，答案是 f_{n-m,m}。

关于多项式的部分，先欠着。