题目大意是给你n个数，求相邻两数相乘不是完全平方数的排列数。
一开始看到这题的时候，本人便想给相乘为完全平方数的数对建边，然后就写萎了...
后来通过集体智慧发现这个重要性质：对于自然数a,b,c，若a*b为完全平方数，且b*c为完全平方数，那么a*c就是完全平方数。（我居然没想到）因此就可以对这n个数进行分组，使得每一组中两个数两两相乘为完全平方数，不同组的数两两相乘不是完全平方数。假设分成tot组，第i组的数的个数为num[i]。这也就等同于相同的数不能相邻的排列问题。
于是通过PY就得到了动规的做法：
定义数组dp[i,j]，其中i表示前i组数，j表示有多少对相邻的同组的数（这也等价于有j个地方需要插入其他的数），而dp[i,j]就表示在当前状态下的方案数。那么最终答案就是dp[tot,0]。
定义m为前i-1组数的元素个数之和，在dp过程中维护。
当新加入第i组数的时候，把这num[i]个数分成k份（方案数是C(num[i]-1,k-1)），插入到m+1个空位中。
此时需要分类讨论：
在这m+1个空位中，有j个空位是特殊的，若插入其中会影响新生成的排列的相邻同组数的数目。于是设k份中的p份插入这j个空位中，剩下k-p份插入m+1-j个空位中。
就可以得到dp[i,j+num[i]-k-p]+=dp[i-1,j]*C(num[i-1],k-1)*C(j,p)*C(m+1-j,k-p);
这我一开始也不是很理解...
当然代码与这里有所差异。
注：因为dp是基于每一组数中的元素相同的前提的，所以最后答案还要乘以每一组数的A(num[i],num[i])。
#include<bits/stdc++.h>
using namespace std;
const int N=,MOD=;
long long num[N],c[N][N];
long long dp[N][N],a[N];
int tmp,n,tot,example[N];
bool key;
bool ask(int x,int y)
{
long long re=;
re*=x;
re*=y;
long long f=sqrt(re);
if(f*f==re) return ;
return ;
}
int main()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>tmp;
key=;
for(int j=;j<=tot;j++)
{
if(ask(tmp,example[j]))
{
num[j]++;
key=;
break;
}
}
if(key)
{
num[++tot]=;
example[tot]=tmp;
}
}
for(int i=;i<=n;i++)
c[i][]=;
for(int i=;i<=n;i++)
for(int j=;j<=i;j++)
{
c[i][j]=c[i-][j]+c[i-][j-];
c[i][j]%=MOD;
}
int m=;
a[]=;
for(int i=;i<=n;i++)
{
a[i]=a[i-]*i;
a[i]%=MOD;
}
dp[][]=;
long long temp,temp1;
for(int i=;i<=tot;i++)
{
for(int j=;j<n&&j<=m+;j++)
{
if(dp[i-][j]==) continue;
for(int k=;k<num[i];k++)
{
temp=dp[i-][j]*c[num[i]-][k];temp%=MOD;
for(int p=;p<=k+&&p<=j+num[i]--k;p++)
{
temp1=temp*c[j][p];temp1%=MOD;//本人因为数据溢出炸了几次
dp[i][j+num[i]--k-p]+=(temp1*c[m+-j][k+-p])%MOD;
dp[i][j+num[i]--k-p]%=MOD;
}
}
}
m+=num[i];
}
for(int i=;i<=tot;i++)
{
dp[tot][]*=a[num[i]];
dp[tot][]%=MOD;
}
cout<<dp[tot][]<<endl;
return ;
}