注意到若 \(a_i=c^2r\)，则让 \(a_i:=r\) 答案不会变。
则现在将问题转化为有 \(n\) 个有标号的不同颜色的球，问有多少种排列使得没有同色球相邻，设 \(a_i\) 为颜色为 \(i\) 的球的个数。
我们考虑容斥，我们注意到没有同色球相邻等价于 \(n-1\) 个限制：\(\forall i=1\rightarrow n-1\)，\(i\) 和 \(i+1\) 上的球的颜色不同 。设 \(f(i)\) 表示恰好有 \(i\) 个限制未被满足的方案数，\(g(i)\) 为钦定 \(i\) 个位置的限制未被满足的方案数，注意到这是一个子集反演的形式（把每个位置的限制是否被满足看作集合的元素）（update：经过讨论这似乎是二项式反演，只不过二项式反演和子集反演在求 \(f(0)\) 时是一致的），则 \(f(0)=\sum\limits_{i=0}^{n-1}(-1)^ig(i)\)。
考虑求 \(g(i)\)，我们考虑每种颜色球的贡献。与整体的情况类似，我们认为每一种球也有 \(a_k-1\) 个限制：最终排列完之后第 \(i\) 个球和第 \(i+1\) 个球不能相邻。
注意到如果我们钦定了某个位置的限制不满足，则会把两个球缩到一起。如果钦定有 \(i\) 个限制不满足，最后相当于把这种颜色的球缩成了 \(a_k-i\) 段，由于最后的拼接是关于球的段数的，所以我们写出关于最后剩余球的段数的 EGF： \[
F_k(z)=a_k!\sum\limits_{i=1}^{a_k}\binom{a_k-1}{i-1}\frac{z^i}{i!}
\] 即我们先枚举一个标号的排列，然后选出 \(i-1\) 个位置切断，然后由于 EGF 要把新的段数的标号消掉所以要除以 \(i!\)。
所以有 \(g(i)=(n-i)![z^{n-i}]\prod F_k(z)\)。
由于这题模数是 \(10^9+7\) 而且 \(n\) 比较小，所以用了暴力卷积，否则可以使用分治+NTT 优化至 \(O(n\log^2n)\)。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<bits/stdc++.h>
using namespace std;
int const p=1e9+7;
int a[305],b[305],fac[305],inv[305];
vector<int>v[305];
bool visited[305];
int pw(int x,int y)
{
int res=1;
while(y)
{
if(y&1)res=1ll*res*x%p;
x=1ll*x*x%p;
y>>=1;
}
return res;
}
int main()
{
int n,m=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++)
{
fac[i]=1ll*fac[i-1]*i%p,inv[i]=1ll*inv[i-1]*pw(i,p-2)%p;
if(visited[i])continue;
m++;b[m]=1;
for(int j=i+1;j<=n;j++)
{
int t=(int)(sqrt(((long double)a[i])*a[j])+1e-12);
if(1ll*t*t==1ll*a[i]*a[j])visited[j]=1,b[m]++;
}
}
vector<int>res(1,1);
for(int i=1;i<=m;i++)
{
v[i].resize(b[i]+1);
for(int j=1;j<=b[i];j++)v[i][j]=1ll*fac[b[i]-1]*inv[j-1]%p*inv[b[i]-j]%p*inv[j]%p;
vector<int>tmp(res.size()+v[i].size()-1);
for(int j=1;j<=b[i];j++)
for(int k=0;k<res.size();k++)
tmp[j+k]=(tmp[j+k]+1ll*v[i][j]*res[k])%p;
res=tmp;
}
int ans=0;
for(int i=0;i<res.size();i++)
ans=(ans+1ll*((i&1)?p-1:1)*fac[n-i]%p*res[n-i])%p;
for(int i=1;i<=m;i++)ans=1ll*ans*fac[b[i]]%p;
printf("%d",ans);
return 0;
}
|