DDOSvoid's Blog

CF 840C On the Bench

发表于 更新于 分类于
本文字数： 4.7k 阅读时长 ≈ 4 分钟

题目描述

https://www.luogu.com.cn/problem/CF840C

简要题意：给定一个长度为 $n$ 的序列 $a_i$，问有多少排列 $p$ 满足对于所有 $i\in[2,n]$，$a_{p_{i-1}}\times a_{p_i}$ 不是完全平方数

$n \le 300,a_i\le 10^9$

Solution

我们考虑首先将每个数出现偶数次的质因子都去掉后，容易得到满足条件的排列是相等的数不能相邻的排列

那么题意被我们转换成求一个类似多重集的交错排列的东西，我们考虑组合容斥

令 $f_k$ 表示至少有 $k+1$ 个相同的数相邻，$g_k$ 表示恰好有 $k+1$ 个相同的数相邻

容易得到 $f_k=\sum_{i=k}^{n}\binom{i}{k}g_i\Leftrightarrow g_k=\sum_{i=k}^n(-1)^{i-k}\binom{i}{k}f_i$，答案即为 $g_0=\sum_{i=0}^n(-1)^if_i$

我们考虑对于 $m$ 个相同的数，我们将其分为 $k$ 个连续段，那么他们对答案的贡献是 $m-k$

所以我们考虑这样求 $f$，我们求所有数中至少有 $k$ 个连续段的排列个数为 $h_k$，容易得到 $h_k=f_{n-k}$

对于 $h$，我们考虑指数生成函数，那么容易得到对于一种数字，不妨设其有 $m$ 个，那么它的指数生成函数就是 $F(x)=\sum_{i=1}^{m}m!\binom{m-1}{i-1}\frac{x^i}{i!}$，我们把所有数字的生成函数卷起来即可，因为 $\sum m =n$，所以这部分可以做到 $O(n\log ^2n)$

总的时间复杂度为 $O(n\sqrt a_i+n\log ^2n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <map>
#define maxn 310
#define ll long long
#define INF 1000000000
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n, int p = 1000000007) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    return s;
}

const int mod1 = 998244353, mod2 = 1004535809, mod3 = 469762049, G = 3;
const ll mod12 = 1ll * mod1 * mod2;
const int inv1 = pow_mod(mod1, mod2 - 2, mod2), inv2 = pow_mod(mod12 % mod3, mod3 - 2, mod3);
struct Int {
    int x, y, z;

    Int() {}
    Int(int x, int y, int z) : x(x), y(y), z(z) {}
    Int(int v) : x(v), y(v), z(v) {}

    static inline int add(int x, int y, int p) { return (x += y) >= p ? x - p : x; }
    
    inline friend Int operator + (const Int &u, const Int &v) {
        return Int(add(u.x, v.x, mod1), add(u.y, v.y, mod2), add(u.z, v.z, mod3));
    }
    inline friend Int operator - (const Int &u, const Int &v) {
        return Int(add(u.x, mod1 - v.x, mod1), add(u.y, mod2 - v.y, mod2), add(u.z, mod3 - v.z, mod3));
    }
    inline friend Int operator * (const Int &u, const Int &v) {
        return Int(1ll * u.x * v.x % mod1, 1ll * u.y * v.y % mod2, 1ll * u.z * v.z % mod3);
    }
    
    inline int get() {
        ll v = 1ll * add(y, mod2 - x, mod2) * inv1 % mod2 * mod1 + x;
        return (1ll * add(z, mod3 - v % mod3, mod3) * inv2 % mod3 * (mod12 % p) % p + v) % p;
    }
};

typedef std::vector<Int> Poly;
namespace Pol {
    const int N = 4200000;
    Int a[N], b[N], w[N];

    const int Gi1 = pow_mod(G, mod1 - 2, mod1);
    const int Gi2 = pow_mod(G, mod2 - 2, mod2);
    const int Gi3 = pow_mod(G, mod3 - 2, mod3);

    int P[N];
    void init_P(int n) {
        int l = 0; while ((1 << l) < n) ++l;
        for (int i = 0; i < n; ++i) P[i] = (P[i >> 1] >> 1) | ((i & 1) << l - 1);
    }

    void NTT(Int *a, int n, int type) {
        for (int i = 0; i < n; ++i) if (i < P[i]) swap(a[i], a[P[i]]);
        for (int i = 2, m = 1; i <= n; m = i, i *= 2) {
            Int wn = Int(pow_mod(type > 0 ? G : Gi1, (mod1 - 1) / i, mod1),
                        pow_mod(type > 0 ? G : Gi2, (mod2 - 1) / i, mod2),
                        pow_mod(type > 0 ? G : Gi3, (mod3 - 1) / i, mod3));
            w[0] = Int(1); for (int j = 1; j < m; ++j) w[j] = wn * w[j - 1];
            for (int j = 0; j < n; j += i) 
                for (int k = 0; k < m; ++k) {
                    Int t1 = a[j + k], t2 = a[j + k + m] * w[k];
                    a[j + k] = t1 + t2;
                    a[j + k + m] = t1 - t2;
                }
        }
        if (type < 0) {
            Int inv = Int(pow_mod(n, mod1 - 2, mod1), pow_mod(n, mod2 - 2, mod2), pow_mod(n, mod3 - 2, mod3));
            for (int i = 0; i < n; ++i) a[i] = a[i] * inv;
        }
    }

    Poly Mul(const Poly &A, const Poly &B, int n1, int n2) {
        int n = 1; while (n < n1 + n2 - 1) n <<= 1; init_P(n);
        copy_n(A.begin(), n1, a), fill(a + n1, a + n, Int(0));
        copy_n(B.begin(), n2, b), fill(b + n2, b + n, Int(0));
        NTT(a, n, 1); NTT(b, n, 1);
        for (int i = 0; i < n; ++i) a[i] = a[i] * b[i];
        NTT(a, n, -1); Poly ans(n1 + n2 - 1);
        for (int i = 0; i < n1 + n2 - 1; ++i) ans[i] = a[i].get(); 
        return ans;
    }
}  // namespace Pol

ll fac[maxn], inv[maxn];
void init_C(int n) {
    fac[0] = 1; for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % p;
    inv[n] = pow_mod(fac[n], p - 2); for (int i = n - 1; ~i; --i) inv[i] = inv[i + 1] * (i + 1) % p;
}

ll C(int n, int m) { return n < m ? 0 : fac[n] * inv[m] % p * inv[n - m] % p; }

int n, a[maxn];

int num[maxn], s[maxn];
Poly solve(int l, int r) {
    if (l == r) {
        int m = num[l]; Poly A(m + 1); A[0] = Int(0);
        for (int i = 1; i <= m; ++i)
            A[i] = Int(C(m - 1, i - 1) * fac[m] % p * inv[i] % p);
        return A;
    } int m = l + r >> 1;
    return Pol::Mul(solve(l, m), solve(m + 1, r), s[m] - s[l - 1] + 1, s[r] - s[m] + 1);
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; map<vector<int>, int> mp; init_C(n); 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        vector<int> A;
        for (int p = 2; p * p <= a[i]; ++p) {
            if (a[i] % p) continue; int s = 0; 
            while (a[i] % p == 0) ++s, a[i] /= p;
            if (s & 1) A.push_back(p); 
        } if (a[i] > 1) A.push_back(a[i]); ++mp[A];
    } int cnt = 0;
    for (auto [vec, m] : mp) num[++cnt] = m;
    for (int i = 1; i <= cnt; ++i) s[i] = s[i - 1] + num[i];
    Poly res = solve(1, cnt); ll ans = 0; 
    for (int i = 0, opt = 1; i <= n; ++i, opt = -opt)
        ans = (ans + opt * fac[n - i] * res[n - i].get()) % p;
    cout << (ans + p) % p << "\n";
    return 0; 
}