芳乃可爱捏。
近日发现自己的计数水平真的差的没边，索性开了个专题专门来记容斥。
P4448 [AHOI2018初中组] 球球的排列
给出 $m$ 个球，每个球有颜色 $a_i\in[1,n]$。球有编号，求多少种分配顺序使得任意相邻球异色。 $m\le 2000$。
实际上这是已经转化过的题意了。下面简单等价一下。
若 $xy=a^2$ 且 $xz=b^2$，则 $x^2yz=a^2b^2$。于是 $yz=\left(\dfrac{ab}{x}\right)^2$。其实到这里就可以说明 $yz$ 亦是平方数，但是进一步取 $x$ 与 $ab$ 的质因子交集，就可严格证明。
直接钦定是混乱的，考虑一种求方案的惯用手法——捆绑法。不妨把相邻同色的捆绑在一起，这样在刻画状态时更容易处理。设 $b_i$ 表示颜色 $i$ 形成的块数，令 $B=\sum\limits_{i=1}^n b_i$。
假定已确定一组状态 $(b_1,b_2,\cdots,b_n)$，先考虑一种颜色的贡献。考虑划分每个块的大小，再进行相对排列。根据插板，有 $a_i!\dbinom{a_i-1}{b_i-1}$。扩展到多种颜色，那么实际上还要对这所有格块进行排序划分。即 $B!\prod a_i!\dbinom{a_i-1}{b_i-1}\dfrac{1}{b_i!}$。$\dfrac 1{b_i!}$ 的系数是抵消同种色块的相对排序。
发现如果固定 $B$，转移中 $b_i$ 与 $b_{i-1}$ 之间无关，于是设 $f(i,j)$ 表示用了前 $i$ 个颜色的 $\sum\limits_{k=1}^i b_k=j$。枚举 $j$ 以及当前块数 $k$，有转移 $f(i,j+k)\gets f(i-1,j)\times a_{i}\dbinom{a_i-1}{b_i-1}\dfrac{1}{b_i!}$，最终给所有的 $f(n,k)$ 乘上一个系数 $k!$。由于 $m=\sum a_i$，所以事实上复杂度是 $\mathcal O(m^2)$ 的。
对于 $f(n,k)$，由于第一维始终为 $n$，在接下来的叙述中略去这一维度。
考虑容斥的经典形式 $f(S)=\sum\limits_{T\subseteq S} g(T)\iff g(S)=\sum\limits_{T\subseteq S}(-1)^{\vert T\vert -\vert S\vert}f(T)$。套到这道题上，注意到 $f(k)$ 实则上是对所有大小为 $k$ 的集合 $\vert S\vert$ 的和，$g(S)$ 同理。于是直接进行容斥，$g(k)$ 表示 $B=k$ 的方案数。有 $g(B)=\sum\limits_{i=1}^{B}(-1)^{B-i}f(i)$，$g(m)$ 即为答案。