DDOSvoid's Blog

2021牛客多校10 G Game of Death

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

题目描述

https://ac.nowcoder.com/acm/contest/11261/G

简要题意：$n$ 人围成一圈，每个人独立随机地选择一名其他玩家并向其开一枪，开枪是同时的，被命中者立刻阵亡退出游戏，假设所有人的命中概率都为 $p$，问还剩 $k=0,1,2,\cdots,n$ 个人 的概率.

$n\le 3\times 10^5$

Solution

我们考虑容斥，不必精确的计算到底有那些人还活着，我们考虑定义 $f(S)$ 表示只有集合 $S$​ 里的人被枪击，有多少人活着不作考虑，$g(S)$​ 表示集合 $S$ 里的人死了，容易得到 $f(S)$ 中死掉的人一定是 $S$ 的子集，可以得到子集反演 $g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)$

$f(S)$​ 较为容易计算，$f(S)=(1-p+\frac{p(|S|-1)}{n-1})^{|S|}(1-p+\frac{p|S|}{n-1})^{n-|S|}$​，大概就是将人分为圈外和圈内，然后每个人没有命中活着命中圈内的人

可以发现 $f(S)$ 只跟集合大小有关系，$g(S)=\sum_{i=0}^{|S|}(-1)^i\binom{|S|}{i}f(i)$，这显然是一个卷积的形式，答案就是 $\binom{n}{|S|}g(|S|)$，

时间复杂度 $O(n\log 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
#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 300010
#define ll long long
using namespace std;

const int p = 998244353;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1, x = x * x % p)
        if (n & 1) s = s * x % p;
    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 sub(int a, int b) { return (a -= b) < 0 ? a += p : a; }
    inline void inc(int &a, int b) { (a += b) >= p ? a -= p : a; }
    inline void dec(int &a, int b) { (a -= b) < 0 ? a += p : a; }
 
    const int N = 4200000;
    int a[N], b[N];
 
    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) {
        static int w[N]; ll G = 3, Gi = pow_mod(G, p - 2);
        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) {
            ll wn = pow_mod(type > 0 ? G : Gi, (p - 1) / i);
            w[0] = 1; for (int j = 1; j < m; ++j) w[j] = wn * w[j - 1] % p;
            for (int j = 0; j < n; j += i)
                for (int k = 0; k < m; ++k) {
                    int t1 = a[j + k], t2 = 1ll * a[j + k + m] * w[k] % p;
                    a[j + k] = add(t1, t2);
                    a[j + k + m] = add(t1, p - t2);
                }
        }
        if (type < 0) {
            ll inv = pow_mod(n, p - 2);
            for (int i = 0; i < n; ++i) a[i] = inv * a[i] % p;
        }
    }
    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);
        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);
        NTT(a, n, 1); NTT(b, n, 1);
        for (int i = 0; i < n; ++i) a[i] = 1ll * a[i] * b[i] % p;
        NTT(a, n, -1); Poly ans(n1 + n2 - 1); copy_n(a, n1 + n2 - 1, ans.begin());
        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;
}

int n, a, b;
ll pro;

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

    cin >> n >> a >> b; init_C(n); 
    pro = a * pow_mod(b, p - 2) % p; 
    Poly A(n + 1), B(n + 1);
    for (int i = 0; i <= n; ++i) 
        A[i] = pow_mod((1 - pro + pro * (i - 1) % p * pow_mod(n - 1, p - 2)) % p, i) *
            pow_mod((1 - pro + pro * i % p * pow_mod(n - 1, p - 2)) % p, n - i) % p * inv[i] % p;
    for (int i = 0; i <= n; ++i) 
        B[i] = pow_mod(-1, i) * inv[i];
    Poly ans = Pol::Mul(A, B, n + 1, n + 1);
    for (int i = n; ~i; --i) {
        ll res = ans[i] * fac[n] % p * inv[n - i] % p; 
        cout << (res + p) % p << "\n";
    }
    return 0; 
}