CF840C 题解

· · 题解

CF840C On the Bench 题解

前言

提供一个 O(n^2) 的容斥

预处理

注意到

ab=x^2,ac=y^2\Rightarrow a^2bc=x^2y^2\Rightarrow bc=\dfrac{x^2y^2}{a^2}=\left(\dfrac{xy}{a}\right)^2

故相乘是平方数是可以传递的，于是我们如果把不能相邻的 p 之间连一条边，那么就会得到若干个完全图，题目可以简化为每个数有一个颜色 c_i ，求满足相邻数颜色不同的排列的个数

转换

注意到互不相邻这个条件并不好转换，但是如果我们钦定两个数相邻，那么我们就可以把这两个数看作一个数进行后续操作，于是我们考虑子集反演

令全集 U=\{(x,y)|c_x=c_y \} 其中 (x,y) 无序, 对于一个 S\subseteq U，定义 f(S) 为满足 c_x=c_y,x,y 相邻 \Leftrightarrow (x,y)\in S 的排列的数量，g(S)=\sum_{S\subseteq T} f(T)，即要求 f(\varnothing)=\sum_{S} (-1)^{|S|}g(S)，考虑 g(S) 的组合含义，即我们钦定 S 中的数对中的两个数相邻，然后剩下的数随意排序

记 dp(i,j) 为考虑前 i 种颜色，钦定 j 对同色数相邻的方案数，那么有

f(numc,x)=\sum_{|S|=x}g(S),f(\varnothing)=\sum (-1)^{|i|}dp(numc,i)

转移

对于一种颜色，考虑有 i 个数，钦定其中 j 对相邻，那么就相当于说我们先把 i 个数任意排列，再分成 i-j 个连续的段，段之间互相相邻，不同的两段之间的位置关系我们不考虑，那么答案就是任意排列的 i! ，乘上从 i-1 个间隙之间选出 i-j-1 个，插板将其分开的 \binom{i-1}{i-j-1}，最后由于每段之间的位置关系我们暂时不考虑，于是这 i-j 段的 (i-j)! 个排列算作一个，故答案需要除掉一个 (i-j)!

即

transfer(i,j)=\frac{i!\dbinom{i-1}{i-j-1}}{(i-j)!}=\frac{i!(i-1)!}{j!(i-j)!(i-j-1)!}

剩下的跑一个 O(n^2) 的背包即可

统计答案

注意到在背包的过程中，我们并没有考虑不同段之间的位置关系，而有 i 对数被钦定相邻，那么就总共有 n-i 段，则最终的答案实际上是 f(\varnothing)=\sum (-1)^{|i|}(n-i)!\cdot dp(numc,i)

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 310, P = 1e9 + 7;
ll n, a[M], c[M], s[M], fac[M], inv[M], tc = 1, f[M][M], ans = 0;
ll qpow(ll a, ll b, ll res = 1)
{
    for (; b; b >>= 1, a = a * a % P)
        if (b & 1) res = res * a % P;
    return res;
}
int main()
{
    scanf("%lld", &n), fac[0] = 1;
    for (int i = 1; i <= n; i++) scanf("%lld", a + i), fac[i] = fac[i - 1] * i % P;
    inv[n] = qpow(fac[n], P - 2), f[0][0] = 1;
    for (int i = n - 1; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % P;
    for (int i = 1; i <= n; i++)
        if (!c[i])
        {
            c[i] = tc++;
            for (int j = 1; j <= n; j++)
                if ((long long) sqrt(a[i] * a[j]) * (long long) sqrt(a[i] * a[j]) == a[i] * a[j]) c[j] = c[i];
        }
    for (int i = 1; i <= n; i++) s[c[i]]++;
    for (int i = 1; i < tc; i++)
        for (int j = 0; j < s[i]; j++)
        {
            for (int k = j; k <= n; k++)
                f[i][k] =
                    (f[i][k] + f[i - 1][k - j] * fac[s[i]] % P * fac[s[i] - 1] % P * inv[j] % P * inv[s[i] - j] % P * inv[s[i] - j - 1] % P) % P;
        }
    for (int i = 0; i <= n; i++) ans = (ans + (i & 1 ? -1 : 1) * f[tc - 1][i] * fac[n - i] % P) % P;
    if (ans < 0) ans += P;
    printf("%lld\n", ans);
    return 0;
}