前言:
如果这场比赛的目的是让我罚坐的话,那它很成功了。半成品...
T1:一个赢家(card)
思路:
显然,最大值的取值范围为\([2n+1,4n-1]\),我们设最大值为\(x\),则对于每种\(x\),有\(⌈\frac{4n-x}{2}⌉\)种构成。我们令\(cnt=⌈\frac{4n-x}{2}⌉\),不妨钦定其中一种为唯一的最大值
T2:排列计数(count)
思路:
显然,要把每个数本身含有的平方数先除掉,然后问题就演变成了对于一个序列,有多少种方案能使相同的数不相邻。这是我们只关注数是否相同,因此我们可以先离散化一下,然后统计每种数出现的次数。接下来考虑\(dp\)。设\(f_{i,j}\)表示放入第\(i\)种数有\(j\)个数不合法的。显然,最后我们要的是\(f_{siz,0}\),\(siz\)为数的种类。考虑如何转移:我们设\(cnt_i\)表示第\(i\)种数的次数,转移方程为
\[f[i][j-x+cnt[i]-k-1]=(f[i][j-x+cnt[i]-k-1]+f[i-1][j]*C(cnt[i]-1,k)%mod*C(j,x)%mod*C(s[i-1]+1-j,k+1-x))%mod;
\]
啥意思捏?就是用当前元素插入不合法的数之间减少\(x\)个不合法的数,有新增\(cnt_i-k\)个不合法的数。我们从\(cnt_i\)个数中选出\(k\)个数将从\(j\)个树中选出的\(x\)个数隔开,然后剩下的\(k-x\)个数插入\(s_{i-1}-j+1\)个合法的数的空隙之间,这样不会产生不合法的数。最后因为数字的下标不同表示的方案不同,所以我们在乘上每种数的全排列的方案数就好啦~~
代码:
$code$
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=605,mod=1e9+7;
int T,n,a[N],b[N],ans,num[N],fac[N],inv[N],s[N],cnt[N],f[N][N];
inline int qpow(int x,int y){int res=1;x%=mod;while(y){if(y&1) res=(res*x)%mod;x=(x*x)%mod;y>>=1;}return res;
}
inline int C(int n,int m){if(n<m) return 0;return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);ios::sync_with_stdio(false);fac[0]=1;for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;inv[N-1]=qpow(fac[N-1],mod-2)%mod;for(int i=N-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;cin>>T;while(T--){cin>>n;ans=0;for(int i=1;i<=n;i++) cnt[i]=0;for(int i=1;i<=n;i++){cin>>a[i];int x=a[i];for(int j=2;j*j<=a[i];j++) while(x%(j*j)==0) x/=(j*j);a[i]=x;b[i]=x;}sort(b+1,b+1+n);int siz=unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++){a[i]=lower_bound(b+1,b+1+siz,a[i])-b;cnt[a[i]]++;}for(int i=1;i<=siz;i++) s[i]=s[i-1]+cnt[i];for(int i=0;i<=siz;i++) for(int j=0;j<=n;j++) f[i][j]=0;f[0][0]=1;for(int i=1;i<=siz;i++){for(int j=0;j<=n-siz;j++){if(!f[i-1][j]) continue;for(int k=0;k<cnt[i];k++){for(int x=0;x<=min(j,k+1);x++){f[i][j-x+cnt[i]-k-1]=(f[i][j-x+cnt[i]-k-1]+f[i-1][j]*C(cnt[i]-1,k)%mod*C(j,x)%mod*C(s[i-1]+1-j,k+1-x))%mod;}}}}ans=f[siz][0];for(int i=1;i<=siz;i++) ans=(ans*fac[cnt[i]])%mod;cout<<ans<<'\n';}return 0;
}