【容斥】 P4448 【[AHOI2018初中组]球球的排列】
skydogli
2020-11-18 19:44:25
机房大哥用生成函数爆搞这题，然后另一个大哥用简单容斥推出了复杂度相同的简洁式子。。。
（我只能在一旁膜拜）
不难发现 $2$ 个数相乘等于完全平方数等价于将两个数的平方因子都除去后两数相等。于是我们转化成给出一些等价类，将所有数其任意排列且相邻的数不在同一等价类中的方案。
直接做不好做，考虑容斥：假设有 $k$ 个等价类，令第 $i$ 个等价类大小为 $a_i$，考虑枚举至少有 $b_i$ 个相邻，那么可以推出：
$$ans=n!\sum_{b_{1\dots k}}\frac{(n-\sum b_i)!}{\prod (a_i-b_i)!}\prod\binom{a_i-1}{b_i}(-1)^{\sum b_i}$$
其意义非常直观：
- 下列计算时令等价类无序，而题目要求的本质不同是序号不同，所以答案要标号。
- 在 $a_i$ 个点中用 $b_i$ 条边将任意相邻两个点固定，那么这个等价类点数为 $a_i-b_i$，总的点数为 $n-\sum b_i$ ，所以本质不同的排列数为$\sum_{b_{1\dots k}}\frac{(n-\sum b_i)!}{\prod(a_i-b_i)!}$
- 对于 $a_i$ 个数，他们放在序列上，你要钦定它们有至少 $b_i$ 次出现相邻，相当于选择所有空隙中的 $b_i$ 个，而空隙有 $a_i-1$ 个，所以有个 $\binom{a_i-1}{b_i}$ 的组合数。
- 钦定了至少，所以要容斥，带个 $-1$ 的系数。
直接做的时间复杂度是 $O(n^2)$ 的。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define Mod 1000000007
#define MN 305
int n,a[MN],F[MN],siz[MN];
bool chk(int a){
int b=sqrt(a)+1e-9;
return b*b==a;
}
int fac[MN],dfac[MN],inv[MN];
int f[MN],tmp[MN],g[MN],ans;
int C(int m,int n){
if(m<n)return 0;
return fac[m]*dfac[n]%Mod*dfac[m-n]%Mod;
}
signed main(){
scanf("%lld",&n);
fac[0]=dfac[0]=fac[1]=dfac[1]=inv[1]=1;
for(int i=2;i<=n;++i){
fac[i]=fac[i-1]*i%Mod;
inv[i]=(Mod-Mod/i)*inv[Mod%i]%Mod;
dfac[i]=dfac[i-1]*inv[i]%Mod;
}
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
for(int i=1;i<=n;++i)F[i]=i;
for(int i=1;i<=n;++i){
siz[F[i]]++;
for(int j=i+1;j<=n;++j)
if(chk(a[i]*a[j])){
F[j]=F[i];
}
}
f[0]=1;int sz=0;
for(int i=1;i<=n;++i){
if(!siz[i])continue;
for(int j=0;j<=sz;++j)tmp[j]=f[j],f[j]=0;
for(int j=0;j<siz[i];++j){
g[j]=dfac[siz[i]-j]*C(siz[i]-1,j)%Mod;
if(j&1)g[j]=Mod-g[j];
for(int k=0;k<=sz;++k){
f[j+k]=(f[j+k]+g[j]*tmp[k])%Mod;
}
}
sz+=siz[i]-1;
}
for(int i=0;i<=sz;++i){
ans=(ans+f[i]*fac[n-i])%Mod;
}
for(int i=1;i<=n;++i){
ans=ans*fac[siz[i]]%Mod;
}
sort(a+1,a+1+n);
int lst=0;
printf("%lld\n",ans);
return 0;
}
```
后面的部分可以做到 $O(n\log^2n)$，前面的大概能用简单做法做到 $O(n\pi(a^{\frac{1}{3}}))$ ，硬上 ```pollard-rho``` 能做到 $O(na^{\frac{1}{4}})$ 。
而通过分析可以获得一个期望复杂度 $O(na^{\frac{1}{6}})$ 的复杂度：先把 $a^{\frac{1}{6}}$ 以内的因数除去。再跑```pollard-rho```，因为若存在一个不超过 $a^{\frac{1}{3}}$ 的因子，```pollard-rho```在期望下能在 $O(a^{\frac{1}{6}})$ 的时间内找到。而我们这题要除去的是平方因子，也就是要找到类似 $p^2q$ 的东西，显然是有一个不超过 $a^{\frac{1}{3}}$ 的。但这个东西的问题在我们不知道何时中止，所以可能没有什么实际意义？