DDOSvoid's Blog

2022牛客多校11 L Indjy and the mex

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

题目描述

https://ac.nowcoder.com/acm/contest/38727/L

简要题意：给定一个多重集 $S$，满足 $S$ 中的元素都在 $[0,n]$，且 $|S|=n$，求由 $S$ 组成的长度为 $n$ 的序列的价值和，一个序列的价值定义为它的所有区间的 $mex$ 的和

$n\le 10^5$

Solution

令 $a_i$ 表示 $S$ 中 $i$ 的出现次数，我们首先考虑枚举区间的组成 $b_i$，满足 $\forall i\in[0,n],0\le b_i\le a_i$，对于 $mex$ 为 $k$ 的答案，我们考虑枚举 $i\in [0,k-1]$，在 $[0,i]$ 都出现至少一次的时候记一次答案，这样正好记 $k$ 次答案，形式化的写，答案即为

考虑枚举 $\sum_{i=0}^nb_i$ 统计答案，考虑生成函数 $f_k(x)=\sum_{i=0}^{a_k}\frac{x^i}{(a_k-i)!i!}$，令 $g_k(x)=f_k(x)-\frac{1}{a_k!}$ 表示至少是 $1$，那么答案为

我们考虑分治计算，维护区间 $f$ 的乘积、区间 $g$ 的乘积以及 $\sum_{i=l}^rg_l\cdots g_if_{i+1}\cdots f_{r}$ 即可，时间复杂度 $O(n\log^2 n)$

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 998244353;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; }
inline int mul(initializer_list<int> lst) { int s = 1; for (auto t : lst) s = mul(s, t); return s; }
int pow_mod(int x, int n) {
    int s = 1;
    for (; n; n >>= 1, x = mul(x, x))
        if (n & 1) s = mul(s, x);
    return s; 
}

typedef std::vector<int> Poly;
namespace Pol {
    inline int add(int a, int b) { return (a += b) >= p ? a -= p : a; }
    inline int mul(int a, int b) { return 1ll * a * b % p; }
    
    const int N = 4200000; 
    int a[N], b[N];

    const int G = 3;
    const int Gi = pow_mod(G, p - 2);
 
    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);
    }
    vector<int> init_W(int n) {
        vector<int> w(n); w[1] = 1;
        for (int i = 2; i < n; i <<= 1) {
            auto w0 = w.begin() + i / 2, w1 = w.begin() + i;
            int wn = pow_mod(G, (p - 1) / (i << 1));
            for (int j = 0; j < i; j += 2)
                w1[j] = w0[j >> 1], w1[j + 1] = mul(w1[j], wn);
        }
        return w; 
    } auto w = init_W(1 << 21);
    void DIT(int *a, int n) {
        for (int k = n >> 1; k; k >>= 1)
            for (int i = 0; i < n; i += k << 1)
                for (int j = 0; j < k; ++j) {
                    int x = a[i + j], y = a[i + j + k];
                    a[i + j + k] = mul(add(x, p - y), w[k + j]), a[i + j] = add(x, y);
                }
    }
    void DIF(int *a, int n) {
        for (int k = 1; k < n; k <<= 1)
            for (int i = 0; i < n; i += k << 1)
                for (int j = 0; j < k; ++j) {
                    int x = a[i + j], y = mul(a[i + j + k], w[k + j]);
                    a[i + j + k] = add(x, p - y), a[i + j] = add(x, y);
                }
        int inv = pow_mod(n, p - 2);
        for (int i = 0; i < n; ++i) a[i] = mul(a[i], inv);
        reverse(a + 1, a + n);
    }
    Poly Mul(const Poly &A, const Poly &B) {
        int n = 1, n1 = A.size(), n2 = B.size(); while (n < n1 + n2 - 1) n <<= 1; init_P(n);
        for (int i = 0; i < n1; ++i) a[i] = add(A[i], p);
        for (int i = 0; i < n2; ++i) b[i] = add(B[i], p);
        fill(a + n1, a + n, 0), fill(b + n2, b + n, 0);
        DIT(a, n); DIT(b, n);
        for (int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
        DIF(a, n); Poly ans(n1 + n2 - 1); copy_n(a, n1 + n2 - 1, ans.begin());
        return ans;
    }
    Poly MMul(const Poly &A, const Poly &B, int len) { //减法卷积
        int n = 1; while (n < 2 * len - 1) n <<= 1; init_P(n);
        for (int i = 0; i < len; ++i) a[i] = add(A[i], p);
        for (int i = 0; i < len; ++i) b[i] = add(B[i], p);
        fill(a + len, a + n, 0), fill(b + len, b + n, 0); reverse(b, b + len);
        DIT(a, n); DIT(b, n);
        for (int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]);
        DIF(a, n); Poly ans(len);
        copy_n(a, len, ans.begin()); reverse(ans.begin(), ans.end());
        return ans;
    }
}  // namespace Pol

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

int n, a[maxn];

tuple<Poly, Poly, Poly> solve(int l, int r) {
    if (l == r) {
        Poly A(a[l] + 1), B, AB;
        for (int i = 0; i <= a[l]; ++i) A[i] = mul(inv[i], inv[a[l] - i]);
        B = A; A[0] = add(A[0], p - inv[a[l]]); AB = A; return make_tuple(A, B, AB); 
    } int m = l + r >> 1; 
    auto [lA, lB, lAB] = solve(l, m); auto [rA, rB, rAB] = solve(m + 1, r);
    Poly A = Pol::Mul(lA, rA), B = Pol::Mul(lB, rB), AB1 = Pol::Mul(lAB, rB), AB2 = Pol::Mul(rAB, lA);
    int l1 = AB1.size(), l2 = AB2.size(), L = max(l1, l2); Poly AB(L);
    for (int i = 0; i < L; ++i) {
        if (i < l1) AB[i] = add(AB[i], AB1[i]);
        if (i < l2) AB[i] = add(AB[i], AB2[i]);
    } return make_tuple(A, B, AB); 
}

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

    cin >> n; init_C(n); 
    for (int i = 0; i <= n; ++i) cin >> a[i];
    auto [A, B, AB] = solve(0, n); int ans = 0;
    for (int i = 0; i <= n; ++i) ans = add(ans, mul({ fac[i], fac[n - i + 1], AB[i] }));
    cout << ans << "\n";
    return 0;
}