[组合计数] [容斥] [递推] P4448 球球的排列
_Cheems
·
·
个人记录
前言
借鉴 \rm skydogli 的题解，但更加详细。
题意
给定序列 a_1...a_n，求出它有多少种不同的排列，使得 \forall i<n,a_i*a_{i+1} 不为完全平方数。
注意“不同”指的是原下标不同。
思路
- 一个重要的性质：xy=p^2，yz=q^2。则 xz=p^2q^2/y^2，也是完全平方数。
我们发现，完全平方数是有传递性的，可以用并查集维护这个关系。
因此题目可被转述为：给定 m 个集合，求同一集合内的元素不相邻的排列数量？
有容斥的影子了。令 P_i 表示至少 i 组非法相邻，显然有：
ans = \sum\limits_{i=0}^{n-1} (-1)^iP_i
直接算 P_i 还是不好做，考虑贡献法。令 B 表示总共的非法相邻数，再设 b_i 表示 i 集合中至少有 b_i 组相邻，该集合大小为 a_i
- 又一个重要的性质：a_i 个数，分为若干组使得有 b_i 组相邻。则一定会分成 a_i - b_i 组。
我们把相邻看成连一条边，那么需要在 a_i-1 条边中选 b_i 条，有 a_i-1-b_i 条未被选择，它们把序列分为了 a_i-b_i 段。
进一步的，我们发现 i 集合产生 b_i 组相邻的方案数是：
a_i!C_{a_i-1}^{b_i}
即：先打乱序列，然后分为 a_i-b_i 段产生 b_i 组相邻。
接着，我们又发现原序列共有 n-\sum b_i = n - B 段。
由于上面已经算出每个集合内部的方案数，且不同集合之间不会干涉。因此只需再算出所有段的排列即可。
注意：我们认为相同颜色的段本质相同，否则会算重。
这就是个多重集排列嘛：
（用了容斥，所以不用关心集合间的关系，即谁把谁隔开了之类的）
\frac {(n-B)!}{\prod (a_i - b_i)!}
那么相乘得到：
\frac {(n-B)!}{\prod (a_i - b_i)!}\prod a_i!C_{a_i-1}^{b_i}
然后递推算出答案即可。具体的，设 f_{i,j} 表示考虑前 i 个集合，B=j 时上式的值。把 (n-B)! 单独拎出来最后再算即可。
复杂度 O(n^2)，足够过此题。
提交记录