题解：[AHOI2018初中组] 球球的排列

有一个结论，如果 $a\times b$，$a\times c$ 都是完全平方数，那么 $b\times c$ 也是完全平方数。从质因数的角度看是比较容易理解的（$b$ 和 $c$ 的质因子的指数对 $2$ 同余）。

考虑容斥，用至少 $0$ 对不合法的减去至少 $1$ 对不合法的加上至少 $2$ 对不合法的……。

然后把 $n$ 个数按照是否形成完全平方数分成 $m$ 类，第 $i$ 类的 $c_i$ 个数必然是被拆成若干段塞进了最终的序列里，加入被拆成了 $i$ 段，那么显然就是产生了 $(m-i)$ 对不合法的数（注意是对数不是个数）。设 $g_{i,j}$ 表示大小为 $i$ 的块产生了 $j$ 对不合法的数，即分成了 $(i-j)$ 段。那么选 $(i-j)$ 个数作为段头，剩下的随便放，则有

$$g_{i,j}=C_i^{i-j}{A}_i^j$$

然后设 $f_{i,j}$ 表示安排了前 $i$ 类数，产生了 $j$ 对不合法的方案数，则直接 dp 转移即可。

$$f_{i,j}=\sum f_{i-1,j-k}\times g_{c_i,k}$$

$f_{m,i}$ 则为一开始要求的 $i$ 对不合法的，此时还没考虑块与块之间的重排，最后记得乘上 $(n-i)!$。