CF 840 C

CF 840 C

这,首先要将问题进行转化.

首先,如果(a imes c)是一个perfect square,而(b imes c)也是,那么(a imes b)就也是一个perfect square.

然后,我们就可以将所有的(n)个数分为(tot)个group,每一group的数两两不能相邻.

据说这就成了一个经典问题......那反正我是不会哒.

看了一发题解.

于是开始DP啊.

设(cnt[i])为第(i)个group的数的个数,(sum[i])为前(i)个group的数的个数总和,(dp[i][j])为将前(i)个group数以某种方式排列使得有(j)对相邻的数是同一个group的.

接下来进行转移,首先枚举(k)为将第(i+1)个分成(k)个连续的部分,再枚举(l)为从这连续的(k)个部分中选出(l)个插入前面的(j)对不合法数.

(dp[i+1][j-l+cnt[i+1]-k]=dp[i][j] imes C^{k-1}_{cnt[i+1]-1} imes C^l_j imes C^{k-l}_{sum[i]+1-j})

这是不是很有道理啊.

然后最后答案就是(dp[tot][0] imes Pi_{i=1}^{tot}cnt[i]!)

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
const int MAXN=300;
const int MOD=1e9+7;
int n;
int a[MAXN+10];
int fa[MAXN+10],cnt[MAXN+10];
int find(int x){return (fa[x]==x)?x:(fa[x]=find(fa[x]));}
bool check(ll a){ll b=sqrt(a);return b*b==a;}
int dp[MAXN+10][MAXN+10];
int fact[MAXN+10],C[MAXN+10][MAXN+10];
int AddMod(int x,int y){int z=x+y;return (z>=MOD)?(z-MOD):z;}
void SelfAddMod(int& x,int y){x+=y;if(x>=MOD)x-=MOD;}
int sum[MAXN+10],f[MAXN+10],tot;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",a+i),fa[i]=i;
	for(int i=1;i<n;++i)
		for(int j=i+1;j<=n;++j)
			if(check((ll)a[i]*a[j]))fa[find(i)]=find(j);
	for(int i=1;i<=n;++i)++cnt[find(i)];
	for(int i=1;i<=n;++i)if(cnt[i])f[++tot]=cnt[i],sum[tot]=sum[tot-1]+f[tot];
	fact[0]=1;
	for(int i=1;i<=n;++i)fact[i]=(ll)fact[i-1]*i%MOD;
	C[0][0]=1;
	for(int i=1;i<=n;++i){C[0][i]=1;for(int j=1;j<=i;++j)C[j][i]=AddMod(C[j-1][i-1],C[j][i-1]);}
	dp[0][0]=1;
	for(int i=0;i<tot;++i)
		for(int j=0;j<=n;++j)
			for(int k=1;k<=f[i+1];++k)
				for(int l=0;l<=k&&l<=j;++l)
					SelfAddMod(dp[i+1][j-l+f[i+1]-k],(ll)dp[i][j]*C[k-1][f[i+1]-1]%MOD*C[l][j]%MOD*C[k-l][sum[i]+1-j]%MOD);
	int ans=dp[tot][0];
	for(int i=1;i<=tot;++i)ans=(ll)ans*fact[f[i]]%MOD;
	printf("%d",ans);
	return 0;
}