CF840C On the Bench

【题解】CF840C On the Bench

题目描述：

给定一个序列 $a(a_i\le 10^9)$，长度为 $n(n\le 300)$。

试求有多少 $1$ 到 $n$ 的排列 $p_i$，满足对于任意的 $2\le i\le n$ 有 $a_{p_{i-1}}\times a_{p_i}$ 不为完全平方数，答案对 $10^9+7$ 取模。

题目分析：

（我竟然场切了，太离谱了）

如果对于这个题面硬做的话，其实就是若 $a_i \times a_j$ 不为完全平方数，则连边 $(i,j)$。
问题就转化为了给定一张图，求其哈密顿路的条数，这个东西显然不能做。
所以也就是说这张图必然存在某些特殊性质。
考虑若 $A \times B$ 为完全平方数那么意味着什么呢，考虑将 $A,B$ 写成它的标准分解式也就是 $A = \prod p_i^{a_i}$，$B = \prod p_i^{b_i}$，这样 $A \times B = \prod p_i^{a_i + b_i}$，其为完全平方数也就是对于每一个 $a_i + b_i$ 其均为偶数，即 $a_i \equiv b_i \pmod 2$。
所以我们可以一开始就对所有的数分解为其标准分解式，然后将其指数模 $2$，这样的问题就转化为了相邻两个位置上的数不相等。
可以考虑一种一种数地插入，然后 $dp$ 去统计这个过程的方案数。
也就是设 $dp_{i,j}$ 表示插入了前 $i$ 种数，有 $j$ 个位置存在相邻两个位置的数相等。
转移就是考虑新加入的这一种数，会将多少个原本相邻且相等的位置占据，又会产生多少个相邻且相等的位置，带上一些组合系数去转移即可。
可以发现当我们确定了当前新加入的数内部会造成多少个相邻且相等的位置时，我们就相当于将其分成了固定的几段，也就是可以视为几个小球插入到序列里。
因为所有的数的出现次数之和为 $n$，所以复杂度为 $O(n^3)$。

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 305;
const int MOD = 1e9+7;
int a[N],b[N],tot,dp[N][N],pre[N],inv[N],fac[N];
int power(int a,int b){
	int res = 1;
	while(b){
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
int binom(int n,int m){
	if(n < m || n < 0 || m < 0)	return 0;
	return fac[n] * inv[m] %MOD * inv[n-m] % MOD;
}
int get(int x){
	int tmp = 1;
	for(int i=2; i*i<=x; i++){
		int cnt = 0;
		while(x % i == 0){
			x /= i,++cnt;
		}
		if(cnt & 1)	tmp = tmp * i;
	}
	if(x > 1)	tmp = tmp * x;
	return tmp;
}
void add(int &a,int b){
	a = (a + b) % MOD;
}
signed main(){
	int n;scanf("%lld",&n);
	for(int i=1; i<=n; i++)	scanf("%lld",&a[i]);
	bool flag = false;
	for(int i=1; i<=n; i++){
		if(a[i] == 0)	flag = true;
	}
	if(flag){
		if(n == 1)	printf("1\n");
		else	printf("0\n");
		return 0;
	}
	for(int i=1; i<=n; i++)	a[i] = get(a[i]);
	sort(a+1,a+n+1);
	int sz = 1,pos = 1;
	for(int i=2; i<=n; i++){
		if(a[i] == a[pos])	++sz;
		else	b[++tot] = sz,sz = 1,pos = i;
	}
	b[++tot] = sz;
	
	for(int i=1; i<=tot; i++)	pre[i] = pre[i-1] + b[i];
	fac[0] = 1;
	for(int i=1; i<=n; i++)	fac[i] = (fac[i-1] * i)%MOD;
	inv[n] = power(fac[n],MOD-2);
	for(int i=n-1; i>=0; i--)	inv[i] = (inv[i+1] * (i+1)) % MOD;
	dp[0][0] = 1;
	for(int i=0; i<tot; i++){
		for(int j=0; j<=pre[i]+1; j++){
			if(!dp[i][j])	continue;
			for(int k=0; k<=b[i+1]-1; k++){   //i 新形成了 k 个 
				int p = (b[i+1]-1) - k + 1;  //相当于要放 p 个物品
				int tmp = binom(b[i+1]-1,p-1) * fac[b[i+1]] % MOD;  //阶乘的原因是题目的方案数不同顺序算不同的 
				for(int x=0; x<=j; x++){  //断掉之前的 x 个，即钦定有 x 个放在特殊位置，p - x 个放在不特殊地位置
					add(dp[i+1][j+k-x],
					dp[i][j] * binom(j,x) % MOD * binom(pre[i] + 1 - j,p-x) % MOD * tmp %MOD);
				}
			}
		}
	}
	printf("%lld\n",dp[tot][0]);
	return 0;
}