传送门 [官方题解]http://codeforces.com/blog/entry/53943?locale=en() 我一直以为这场CF没题解，其实是Div2没题解 其实这题并不是很难想，像我这种蒟蒻在赛场上都能想出DP状态和转移，似乎跟题解差不多。然而因为自己太菜，状态设计的不太合理，转移很麻烦，然后就GG了。 题意很简单，就不说了。 大致说下我的做法，首先注意到如果 ab 和 bc 是完全平方数，那么 ab∗bc 也是，所以 ac 也是，故”bad”pairs具有传递性。 然后将原序列分成几组数，每组里的数两两互斥，设 f[i][j] 为前i组数中有j个bad pairs，枚举当前组贡献的bad pairs数量p，和消除的bad pairs数量k，大力 O(n4) 转移一波即可，如果加点前缀和优化的，或许能到 O(n3) . 然而因为自带小常数， O(n4) 能过 转移时我把n个东西分成k组，每组不少于一个的方案数用split[n][k]保存，这样有利于减少代码复杂度。 解锁成就，在赛场上嘴巴ACdiv2E
#include<cstdio> #include<algorithm> typedef long long ll; const int mo=1000000007,N=305; int n,f[N][N],i,j,k,a[N],w,c[N],d[N],l,fac[N],s[N],p,x,C[N][N],split[N][N],ans; bool b[N]; inline bool isps(ll x){ ll l=1,r=mo-7,m; while(l<r){ m=(l+r)>>1; if(m*m<x)l=m+1; else r=m; } return l*l==x; } bool cmp(int a,int b){ return a>b; } int main(){ scanf("%d",&n); for(i=1;i<=n;++i)scanf("%d",a+i); for(i=1;i<=n;++i)if(!b[i]){ for(j=i+1,w=0;j<=n;++j)if(isps(1ll*a[i]*a[j]))c[++w]=j; for(j=1;j<=w;++j)b[c[j]]=1; d[++l]=++w; } for(i=*fac=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mo; for(i=**C=1;i<=n;++i) for(j=*C[i]=1;j<=i;++j)C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo; split[1][1]=1; for(i=2;i<=n;++i) for(j=2,split[i][1]=1;j<=i;++j) for(k=1;k<=i-j+1;++k)split[i][j]=(split[i][j]+split[i-k][j-1])%mo; std::sort(d+1,d+l+1,cmp); for(i=1;i<=l;++i)s[i]=s[i-1]+d[i]; f[1][d[1]-1]=1; for(i=2;i<=l;++i)//考虑前i组 for(j=0;j<=s[i]-i;++j){//考虑有j对"bad neighbor" int&x=f[i][j]; for(k=1;k<=d[i];++k)//将第i组分成k组 for(p=0;p<=k;++p)//有p组挡在 "bad neighbor" 中间 if(j+p+k>=d[i] && s[i-1]+1>=j+p-(d[i]-k)) x=(x+1ll*f[i-1][j+p-(d[i]-k)]*split[d[i]][k]%mo* C[j+p-(d[i]-k)][p]%mo*C[s[i-1]+1-j-p+(d[i]-k)][k-p]%mo)%mo; //printf("f[%d][%d]=%d\n",i,j,x); } for(i=1,ans=*f[l];i<=l;++i)ans=1ll*ans*fac[d[i]]%mo; printf("%d\n",ans); return 0; }