cf 840C On the Bench（相邻数乘积不能是平方数）

201709 （ACM）动态规划----计数

• 如果xy，xz乘积是平方数，那么yz乘积也是平方数。问题转化成：n堆小球，每堆小球个数a[i]，所有小球两两不同，将它们排成一串，相邻的不能在同一堆，问方案数。
• 解法
  
  • dp，f[i][j]表示前i堆有j个相邻。
  • 放置第i堆时，它分成k块，消除了d个原本相邻的。
  • 转移见代码。
  • 参考题解

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<" = "<<a<<endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int mod=1e9+7;
const int N=303;
bool vis[N];
int cb,cc;
int a[N],b[N];
ll jc[N],c[N][N],f[N][N];
vector<int> G[N];
bool che(ll x,ll y) {
    ll t=sqrt(x*y);
    return t*t==x*y;
}
void dfs(int u) {
    if(vis[u]) return ;
    ++cc;
    vis[u]=1;
    rep(i,0,sz(G[u])) dfs(G[u][i]);
}
void init() {
    jc[0]=1;
    rep(i,1,N) jc[i]=jc[i-1]*i%mod; 
    rep(i,0,N) c[i][0]=c[i][i]=1;
    rep(i,0,N) {
        rep(j,1,i) {
            c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
        }
    }
}
void upd(ll &a, ll b) {
    a+=b;
    if(a>=mod) a-=mod;
}
int main() {
    ///
    int n;scanf("%d",&n);
    ///init 
    init();
    ///read
    rep(i,1,n+1) scanf("%d",a+i);
    ///get b
    rep(i,1,n+1) {
        rep(j,i+1,n+1) {
            if(che(a[i],a[j])) {
                G[i].pb(j);
                G[j].pb(i);
            }
        } 
    } 
    rep(i,1,n+1) if(!vis[i]) {
        cc=0;
        dfs(i);
        b[++cb]=cc;
    } 
    ///solve
    int tot=0;
    f[0][0]=1;
    rep(i,1,cb+1) {
        rep(j,0,tot+1) {
            rep(k,1,min(b[i],tot+1)+1) {
                rep(d,0,min(j+1,k+1)) {
                    upd(f[i][j-d+b[i]-k],f[i-1][j]*c[b[i]-1][k-1]%mod*c[j][d]%mod*c[tot+1-j][k-d]%mod);     
                }
            }
        }
        tot+=b[i];
    }
    ll ans=f[cb][0];
    rep(i,1,cb+1) ans=ans*jc[b[i]]%mod;
    printf("%lld\n",ans);
    return 0;
}