一、题目描述：
给你一个长度为 $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 }
四、写题心得：
今天一上午都用来想这个题了，好在绝杀过大样例。
希望不要把我的 $rp$ 用完了，保佑我过初赛吧！
自己想出来这样的题真的很有成就感，所以来写题解了。收获如下：
$1、只要你敢想，什么都有可能！=> Exp++!$
$2、只要\ dp\ 的状态设计得好，乱搞都是可以过题的=> Exp++!$
标签：平方,cc,题解,ll,tot,times,CF840C,dp From： https://www.cnblogs.com/yhy-trh/p/CF840C.html