CF840C. On the Bench

Statement

给你一个长度为 $n$ 的序列 $a_i$。问有多少 $1 \sim n$ 的排列 $p_i$，满足 $\forall i \in [2.. n]$，有 $a_{p_i − 1} \times a_{p_i}$ 不为完全平方数。答案对 $10 ^ 9 + 7$ 取模。

数据范围：$n \le 300$，$1 \le a_i \le 10 ^ 9$。

---

Solution

每个数去掉平方因子后，条件等价于没有两个相等的数相邻。

Algorithm 1

把相同的数分类，假设共 $m$ 种不同的数，其中第 $i$ 种有 $c_i$ 个。记 $f(i, j)$ 表示填入前 $i$ 种数，有 $j$ 对相同的数相邻的方案数；$g(i, j)$ 表示将第 $i$ 种数拆分成块内块间均有序的 $j$ 块的方案数。下面设 $s_i = \sum_{j = 1} ^ i c_j$，$t = j - (c_i - k) + x$。

$$f(i, j) = \sum_{k = 1} ^ {c_i} \sum_{x = 0} ^ k \binom t x \cdot \binom {s_{i - 1} - t + 1} {k - x} \cdot g(i, k) \cdot f(i - 1, t)\\ g(i, j) = \binom {c_i - 1} {j - 1} \cdot c_i !$$

时间复杂度 $O(n ^ 3)$。

Algorithm 2

考虑容斥，设 $f(i)$ 表示有至少 $i$ 对相等的数相邻的方案数，那么答案为 $\sum_{i = 0} ^ {n - 1} (-1) ^ i \cdot f(i)$。

仍然相同的数分类，假设共 $m$ 种不同的数，其中第 $i$ 种有 $c_i$ 个。设 $g(i, j)$ 表示在前 $i$ 种数中绑定 $j$ 对数的方案数。

$$g(i, j) = \sum_{k = 0} ^ {c_i - 1} g(i - 1, j - k) \cdot \frac{c_i ! \cdot \binom{c_i - 1} k}{(c_i - k)!}$$

先假设有顺序，分子是从这 $c_i - 1$ 个空隙里选择 $k$ 个连起来；分母则是去掉顺序，留到下面在乘排列数。

所以答案为 $\sum_{i = 0} ^ {n - 1} (-1) ^ i \cdot (n - i) ! \cdot g(m, i)$。

时间复杂度 $O(n ^ 2)$，可以使用分治 MTT 优化到 $O(n \log ^ 2 n)$。

---

Code

Algorithm 1

#include <bits/stdc++.h>
typedef long long LL; const int N = 307, V = 1e9, mod = 1e9 + 7;
LL qpow(LL a, int b) {
    LL s = 1;
    while(b) {
        if(b & 1) s = s * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return s;
}
int n, m = 0, c[N], s[N]; LL fac[N], invf[N], f[N][N], g[N][N], ans = 0;
std::vector<int> vec; std::map<int, int> mp;
LL C(int n, int m) { return fac[n] * invf[m] % mod * invf[n - m] % mod; }
int main() {
    scanf("%d", &n), fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    invf[n] = qpow(fac[n], mod - 2);
    for(int i = n; i; i--) invf[i - 1] = invf[i] * i % mod;
    for(int i = 2; i * i <= V; i++) vec.emplace_back(i * i);
    for(int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        for(int y : vec) while(x % y == 0) x /= y;
        mp[x]++;
    }
    for(auto p : mp) c[++m] = p.second, s[m] = s[m - 1] + c[m];
    f[0][0] = 1;
    for(int i = 1; i <= m; i++) for(int k = 1; k <= c[i]; k++) { 
        g[i][k] = C(c[i] - 1, k - 1) * fac[c[i]] % mod;
        for(int j = 0; j < n; j++) for(int x = 0; x <= k; x++) {
            int t = j - (c[i] - k) + x;
            f[i][j] = (f[i][j] + C(t, x) * C(s[i - 1] - t + 1, k - x) % mod
                * g[i][k] % mod * f[i - 1][t]) % mod;
        }
    }
    return printf("%lld\n", f[m][0]), 0;
}

Algorithm 2

#include <bits/stdc++.h>
typedef long long LL; const int N = 307, V = 1e9, mod = 1e9 + 7;
LL qpow(LL a, int b) {
    LL s = 1;
    while(b) {
        if(b & 1) s = s * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return s;
}
int n, m = 0, c[N]; LL fac[N], invf[N], g[N][N], ans = 0;
std::vector<int> vec; std::map<int, int> mp;
LL C(int n, int m) { return fac[n] * invf[m] % mod * invf[n - m] % mod; }
int main() {
    scanf("%d", &n), fac[0] = 1;
    for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
    invf[n] = qpow(fac[n], mod - 2);
    for(int i = n; i; i--) invf[i - 1] = invf[i] * i % mod;
    for(int i = 2; i * i <= V; i++) vec.emplace_back(i * i);
    for(int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        for(int y : vec) while(x % y == 0) x /= y;
        mp[x]++;
    }
    for(auto p : mp) c[++m] = p.second;
    g[0][0] = 1;
    for(int i = 1; i <= m; i++) for(int j = 0; j < n; j++)
        for(int k = 0; k < std::min(c[i], j + 1); k++)
            g[i][j] = (g[i][j] + g[i - 1][j - k] * fac[c[i]] % mod *
                C(c[i] - 1, k) % mod * invf[c[i] - k]) % mod;
    for(int i = 0; i < n; i++)
        ans = (ans + (i & 1 ? -1 : 1) * fac[n - i] * g[m][i]) % mod;
    return printf("%lld\n", (ans + mod) % mod), 0;
}