CF840C On the Bench

Description

给定长度为 $n$ 的序列 $\{a\}$ ，求 $\{a\}$ 有多少种排列，满足任意相邻两个数的乘积不是完全平方数。
答案对 $10^9+7$ 取模。
$n\leq 300$

Solution

把每个数的平方因子除掉，问题转化为满足任意相邻两个数不相同的排列个数。

假设钦定有 $i$ 个数与其前一个数相同时的方案数为 $f_i$ ，那么答案为

$ans=\sum_{i=0}^{n}(-1)^if_i$

考虑怎么求 $f_i$ 。当是同一种数造成的相邻相同对时，它们可能粘在一起也可能分开；如果是不同种的数，那么它们之间互不影响，可以用乘法原理合并。所以我们先求出同一种数造成的对数再合并。

设 $g_{i,j}$ 表示第 $i$ 种数有 $j$ 个相邻相同对的方案数。所有的相邻相同对可以背包合并各个 $g$ 得到。

假设第 $i$ 种数有 $x$ 个。如果依次去给钦定相同的找与之配对的数，那么第一个的方案数是 $(x-1)$ ，第二个是 $(x-2)$ $\cdots$ ，直至第 $j$ 个为 $(x-j)$ 。再结合从 $x$ 个中选出来这 $j$ 个钦定的数，可得：

$g_{i,j} = \binom{x}{j}(x-1)^{\underline{j}} = \binom{x}{j}\frac{(x-1)!}{(x-1-j)!}$

还有另一种方法来求 $g_{i,j}$ 。考虑 $j$ 个相邻对和划成了 $x-j$ 段是等价的，我们可以从划分段入手。

求解 $g_{i,j}$ 不那么方便的原因就是当我们划好了段以后，每个段内部还可以任意排列，相当于我们还要乘上每个段的 $\text{size}$ 的阶乘。这个很不妙。

我们换个角度来想，考虑将整个排列完全打乱，也就是在外侧乘上 $x!$ 。这个时候再任意划分时，我们多算的部分事实上就是各个段之间的排列。于是我们再分别除以段数的阶乘就可以了。根据这个方法得到的式子为

$g_{i,j}=\frac{x!}{(x-j)!}\binom{x-1}{x-j-1}$

很显然两个式子是等价的。

考虑计算完 $g_{i,j}$ 后，我们相当于只钦定了怎么划分成段，而对于各个段之间的排列并没有算进来（也就是段是无序的）。背包合并时也是无序的。所以最后再乘上阶乘代表钦定各个段之间的排列。

总的来说这个题还是非常不错的，做题时一定要牢记「钦定了什么」「无序还是有序」「多算了什么」「是否可以依次配对」这些问题。比如在这个题中，「钦定了相同的对数」还是不够明确，应该细化到「钦定了哪些数在最后的排列中与前一个数配对」。当这些问题想清楚后，很多的奇怪问题就迎刃而解了。

Code

const int N = 3e2 + 5, M = 1e5, mod = 1e9 + 7;
using namespace std;
int n, num, tot;
int a[N], c[N], o[M], h[N], f[N], fac[N], inv[N], invf[N], g[N][N];
long long p[M];
void Prework(int n){
    for(int i = 2; i <= n; ++i){
        if(!o[i]) p[++num] = i;
        for(int j = 1; j <= num and p[j] * i <= n; ++j){
            o[p[j] * i] = 1;
            if(i % p[j] == 0) break;
        }
    }
    for(int i = 1; i <= num; ++i)
        p[i] = p[i] * p[i];
}
int binom(int n, int m){
    if(n < 0 or m < 0 or n - m < 0) return 0;
    return 1ll * fac[n] * invf[m] % mod * invf[n - m] % mod;
}
int main(){
    
    Prework(1e5);

    r(n);
    fac[0] = fac[1] = inv[0] = inv[1] = invf[0] = invf[1] = 1;
    for(int i = 2; i <= n; ++i) 
        fac[i] = 1ll * i * fac[i - 1] % mod,
        inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod,
        invf[i] = 1ll * invf[i - 1] * inv[i] % mod;
    for(int i = 1; i <= n; ++i){
        r(a[i]);
        for(int j = 1; p[j] <= a[i]; ++j)
            while(a[i] % p[j] == 0) a[i] /= p[j];
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i)
        if(a[i] != a[i - 1]) c[++tot] = 1;
        else ++c[tot];

    for(int i = 1; i <= tot; ++i)
    for(int j = 1; j <= c[i]; ++j)
        g[i][c[i] - j] = 1ll * binom(c[i] - 1, j - 1) * fac[c[i]] % mod * invf[j] % mod;
    
    int len = 1; f[0] = 1;
    for(int i = 1; i <= tot; ++i){
        memset(h, 0, sizeof h);
        for(int k = 0; k < len; ++k)
        for(int j = 0; j < c[i]; ++j)
            (h[k + j] += 1ll * f[k] * g[i][j] % mod) %= mod;
        len += c[i] - 1;
        for(int k = 0; k < len; ++k)
            f[k] = h[k];
    }
    int ans = 0;
    for(int i = 0; i < len; ++i)
        if(i & 1) ans = (ans + mod - 1ll * f[i] * fac[n - i] % mod) % mod;
        else ans = (ans + 1ll * f[i] * fac[n - i] % mod ) % mod;
    w(ans);

    return 0;
}