CF840C 题解-JZTXT

一、题目描述：

　　给你一个长度为 $n$ 的序列 $a_1\sim a_n$，$0 \le a_i \le 1\times 10^9$。

　　求有多少种 $1\sim n$ 的全排列 $b$，使得对于 $i\in [2,n],a_{b_i}\times a_{b_{i-1}}$ 不是完全平方数。

　　本题中完全平方数的定义：若存在某个整数 $k$，使得 $k^2=x$，则 $x$ 是一个完全平方数。

　　答案对 $1\times 10^9+7$ 取模。数据范围：$1\le n\le 300$;

二、解题思路：

　　其实题意就是说相邻两个数的乘积不能为完全平方数。

　　首先容易发现性质：若正整数 $a,b,c$ 满足 $a\times b,a\times c$ 为完全平方数，则 $b\times c$ 为完全平方数。

　　证明：设 $a=x^2\times k,k$ 不含完全平方因子。$x,k$ 均为正整数。

　　若正整数 $k$ 可以写作 $p^2\times q$ 且 $p,q$ 均为正整数且 $p>1$，则认为 $k$ 含有完全平方因子。

　　那么 $a\times b=x^2\times k\times b,a\times c=x^2\times k\times c$。

　　因为 $a\times b,a\times c$ 为完全平方数，则 $b$ 可以写作 $y^2\times k$，$c$ 可以写作 $z^2\times k$。$y,z$ 均为正整数。

　　所以 $b\times c=y^2\times z^2\times k^2=(xyk)^2$ 为完全平方数。

　　注意 $0$ 是一个特殊存在，它与任何数的乘积都是完全平方数。所以有 $0$ 直接输出 $0$ 就可以了。

　　于是我们将这 $n$ 个数分为若干个集合，集合内的数不能相邻，集合外的数可以相邻。设有 $m$ 个集合。

　　于是我们发现这个题转化为一个 $dp$ 计数题。

　　对于一个集合，因为不能集合内的数不能相邻，可以理解成我们有 $k$ 个空需要填。

　　$f_{i,j}$ 表示前 $i$ 个集合还剩下 $j$ 个空需要填的方案数。初值 $f_{0,0}=1$。

　　枚举上一步剩余的空，枚举这一步填上的空，枚举这一步新产生的空，转移就可以了。

　　不过这个代码里面的 $dfs$ 着实鬼畜。也不知道我是怎么想到的。

　　其实这一步是要求有 $x$ 个数要放在 $y$ 个位置的排列数，单数每个位置可以放多个数。

　　乍一看，每个数都有 $y$ 个位置可以选，不就是 $y^x$ 吗？

　　其实这样漏掉了多个数在同一位置上的不同排列方案。

　　但是我肯定不可能枚举每个位置上的数的个数来求排列，只好一开始就求出排列。

　　于是问题变成了顺序在 $y$个位置上放置 $x$ 个数的方案数。

　　这个问题可以递归求解，记忆化搜索做到时间复杂度 $O(n^3)$。

　　于是这道鬼畜的 $dp$ 组合计数题就做完了，时间复杂度 $O(n^3)$。

三、完整代码：

 1 #include<bits/stdc++.h>
 2 #define N 1010
 3 #define ll long long
 4 #define M 1000000007
 5 #define rep(i,l,r) for(ll i=l;i<=r;i++)
 6 #define per(i,r,l) for(ll i=r;i>=l;i--)
 7 using namespace std;
 8 ll n,a[N],fac[N],inv[N],f[N][N];
 9 ll cnt,bel[N],sz[N],sum[N],dp[N][N],vis[N][N];
10 ll C(ll x,ll y){
11     return fac[x]*inv[y]%M*inv[x-y]%M;
12 }
13 ll ksm(ll base,ll q){
14     ll res=1;while(q){
15         if(q&1) res*=base,res%=M;
16         base*=base;base%=M;q>>=1;
17     } return res;
18 }
19 ll dfs(ll tot,ll cc){
20     if(cc==0) return 1;
21     if(vis[tot][cc]) return dp[tot][cc]; vis[tot][cc]=1;
22     rep(i,1,tot) (dp[tot][cc]+=dfs(tot-i+1,cc-1))%=M;
23     return dp[tot][cc];
24 }
25 int main(){
26     ios::sync_with_stdio(false);
27     cin.tie(0);cout.tie(0);
28     cin>>n; rep(i,1,n) cin>>a[i];
29     rep(i,1,n) if(!a[i]){
30         cout<<0<<'\n';
31         return 0;
32     }
33     rep(i,1,n){
34         bool flag=0; rep(j,1,cnt){
35             ll val=a[i]*bel[j],sval=sqrt(val);
36             if(sval*sval==val){flag=1;sz[j]++;break;}
37         } if(!flag) bel[++cnt]=a[i],sz[cnt]=1;
38     }
39     fac[0]=1; rep(i,1,n<<1) fac[i]=fac[i-1]*i%M;
40     rep(i,0,n<<1) inv[i]=ksm(fac[i],M-2);
41     f[0][0]=1; rep(i,1,cnt) sum[i]=sum[i-1]+sz[i];
42     rep(i,1,cnt) rep(j,0,max(sum[i-1]-1,0ll))
43         rep(k,0,min(sz[i],j)) rep(l,0,sz[i]-k){
44             ll t1=C(sz[i],k)*fac[k]%M*C(j,k)%M;
45             ll t2=C(sz[i]-k,l)*fac[l]%M*dfs(sz[i]-l,l)%M;
46             ll res=sz[i]-k-l;
47             ll t3=C(sum[i-1]+1-j,res)*fac[res]%M;
48             (f[i][j-k+l]+=f[i-1][j]*t1%M*t2%M*t3%M)%=M;
49         }
50     cout<<f[cnt][0]<<'\n';
51     return 0;
52 }