CVBB ACM Team

错排改了改，每个物品的限制虽然还是一个，但限制可能有重复。

范围上看 $\mathcal{O}(n^2)$ 就能过。

那我们考虑一下容斥，记 $A_i$ 为每个箱子要装有恰好一个宝石的情况下，第 $i$ 个宝石放在了第 $a_i$ 个箱子的方案集合，方案数就是： \[{\displaystyle \left|\bigcap _{i=1}^{n}{\bar {A_{i}}}\right|=\left|S-\bigcup _{i=1}^{n}A_{i}\right|=|S|-\sum _{i=1}^{n}|A_{i}|+\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|}\]

哦天哪，我们把所有 $j$ 个 $A_i$ 的交集的大小的和，记为 $S_j$，即有 $j$ 个宝石放错，其余随便放的方案数。问题的答案就是： \[\sum_{i=0}^{n} (-1)^i S_i\]

这个 $S_j$ 很好算。记第 $i$ 个箱子有 $b_i$ 个宝石不能放，那么对于放错宝石的数量贡献与否，可以得到多项式： \[\prod_{i} (1 + b_i x)\]

记展开的第 $i$ 项系数为 $c_i$，即 $i$ 个宝石放错的玩法。我们乘上其余宝石乱排的方案数，有 $S_i = c_i (n - i)!$。

那个多项式展开就是个背包，$\mathcal{O}(n^2)$ DP 一下，剩下的都好做。

zzh's comment：多嘴一下，FFT 甚至可以做到 $\mathcal{O}(n\log^{2}n)$。