P5824 十二重计数法

洛谷题面传送门

solution

有 \(n\) 个球和 \(m\) 个盒子。

case 1

球不同，盒不同

答案为 \(m^n\)

case 2

球不同，盒不同，一个盒子内至多一个球

若 \(n>m\) 显然答案为 0

否则，第一个球有 \(m\) 种放法，第二个有 \(m-1\) 种。以此类推，答案为 \(\dfrac{m!}{(m-n)!}\)

case 3

球不同，盒不同，盒子至少一个球。

设 \(f_k\) 表示恰有 \(k\) 个盒子为空的方案数，\(h_k\) 表示钦定 \(k\) 个盒子为空的方案数。

则 \(h_k=\dbinom{m}{k}(m-k)^n\)，且 \(h_k=\sum\limits_{i=k}^{m}\dbinom{i}{k}f_i\)。

二项式反演得 \(f_k=\sum\limits_{i=k}^m (-1)^{i-k}\dbinom{i}{k} h_{i}\)

答案即为 \(f_0=\sum\limits_{i=k}^m (-1)^{i}h_{i}\)

case 4

球不同，盒相同

相当于把 \(n\) 个数划分成 \(m\) 个集合的方案数。

先考虑恰有 \(k\) 个盒子为空的方案数 \(g_k\)。

因为集合互不区分，所以 \(g_k=\dfrac{1}{m!}f_k\) （\(f_k\) 在 case 3 中定义）。

那么这个 case 的答案就是 \(\sum\limits_{i=0}^m g_i\)。

设 \(\{f_k\}_{k=0}^m\) 的指数生成函数是 \(F\)， \(\{(-1)^i\}_{i=0}^m\) 的指数生成函数是 \(G\)，\(\{i^n\}_{i=0}^m\) 的指数生成函数是 \(H\)。

由 \(f_k\) 的展开式可知，\(F=G\times H\)。

NTT 即可求出所有 \(f_k(0\leq k\leq m)\) 。

case 5

球不同，盒相同，盒内至多放一个球

若 \(n>m\)，答案为 0。

否则，答案为 1。

case 6

球不同，盒相同，盒内至少放一个球

答案就是 case 4 中的 \(g_0\)。

case 7

球全部相同，盒子不同。

插板可知答案为 \(\dbinom{n+m-1}{m-1}\)

case 8

球全部相同，盒子不同，盒内至多一个球

相当于从 \(m\) 个盒子中选出 \(n\) 个放球。

答案为 \(\dbinom{m}{n}\)

case 9

球全部相同，盒子不同，盒内至少一个球

插板，\(\dbinom{n-1}{m-1}\)

case 10

设 \(f_{n,m}\) 表示答案。

枚举有几个盒子是空的，然后剩下的盒子都至少有一个小球，将每个盒子内的小球数量减 1，就变成了一个子问题。

即 \(f_{n,m}=\sum\limits_{i=1}^m f_{n-i,i}\)。（注意没有考虑 \(m\) 个盒子是空的情况，因为只有 \(n=m=0\) 时它才对答案有贡献）。

下一步怎么做？一个有趣的办法是注意到 \(f_{n,m-1}=\sum\limits_{i=1}^{m-1} f_{n-i,i}\)。

用 \(f_{n,m}\) 减去 \(f_{n,m-1}\) 得，\(f_{n,m}=f_{n,m-1}+f_{n-m,m}\)。

把 \(n\) 放在第二维，设 \(F_m\) 是 \(\{f_{i,m}\}_{i=0}^n\) 的生成函数，则有 \(F_m=F_{m-1}+x^mF_m\)，即 \(F_m=\dfrac{F_{m-1}}{1-x^m}\)。

把递归式展开得 \(F_m=F_0\times \prod\limits_{i=1}^m \dfrac{1}{1-x^i}\)。

考虑如何计算 \(\prod\limits_{i=1}^m \dfrac{1}{1-x^i}\)。

设 \(G=\prod\limits_{i=1}^m \dfrac{1}{1-x^i}\)。

则 \(\ln G=\sum\limits_{i=1}^m \ln (\dfrac{1}{1-x^i})\)

由于 \(\ln (1-x)=-\sum\limits_{1\leq i} \dfrac{x^i}{i}\)

所以 \(\ln G=\sum\limits_{i=1}^m\sum\limits_{1\leq j}\dfrac{x^{ij}}{j}\)

可以发现，在 \(\bmod ~x^m\) 意义下，有用的 \(j\) 的取值只有 \(m(1+\dfrac{1}{2}+\dfrac{1}{3}+\dots)=O(m\log m)\) 个，所以我们很容易构造出 \(\ln G\)。

然后对 \(\ln G\) 做多项式 exp 就做完了。

case 11

球相同，盒子相同，每个盒子至多装一个球

显然，答案同 case 5

case 12

球相同，盒子相同，每个盒子至少装一个球。

用类似 case 10 的方式考虑。

设 \(g_{n,m}\) 表示本 case 答案。

将所有盒子的球数减 1，接着枚举有几个空盒子，然后剩余部分就变成子问题了。

即 \(g_{n,m}=\sum\limits_{i=0}^m g_{n-m,i}\)。

同样地用做差的方式得出，\(g_{n,m}=g_{n-1,m-1}+g_{n-m,m}\)。

我们惊奇的发现，这个式子和 case 10 的极为相似。

事实上，用同样的放法计算可以发现，本 case 最终的多项式只比 case 10 多乘了一个 \(x^m\)。

于是就做完啦。

code

人傻常数大

hint

我做这个题并不是按 1 ~ 12 的顺序的。

可以优先做 6,12 再做 3,4,10。