G、Game of Death

题目大意

场上共有个人，现在每个人都会随机选择一个其他人开枪，并且成功命中其他人的概率为。

你需要输出场上留下个人的概率，分式对取模。

Solution

考点：子集反演+NTT

首先考虑状态设计，我们让代表被击中的是集合的概率，我们让代表被击中的是子集的概率。

所以我们可以得出。

接下来根据子集反演的公式，我们可以得出。

我们就把问题转变成求击中概率是子集的概率了，这个是比较好求的，如果我们假设代表开枪没打中人的概率。

集合中的人只能开枪没打中或者打中了中除自己以外的某个人，由于每个人都是独立的，概率直接做乘法即可；对于集合外的人，他们只能开枪没打中或者打中了集合中的某个人，同样做出乘法就可以算到。

然后又可以发现和只和集合大小有关和具体选择了那个集合没有关系。

所以我们假设是被击中集合大小为的所有概率之和，那么他就是行的答案。

然后后面那个求和又可以转换成卷积的形式快速求解到，我们把看成，那么后面这个式子就变成了定值的多项式，直接让，把就可以求解到后面的答案了。

const int N = 3e5 + 7; // 2^21

int n, a, b, p, q;
int jc[N], inv[N], G[N];

namespace NTT {
    int limit;
    vector<int> A, B, rev;
    inline int add(int x, int y) { return x += y, x >= MOD ? x - MOD : x; }
    inline int mul(int x, int y) { return 1ll * x * y % MOD; }
    int qpow(int x, int y) {
        int res = 1;
        for (; y; y >>= 1, x = mul(x, x)) if (y & 1) res = mul(res, x);
        return res;
    }
    void init() {
        int ed = n * 2, bit = -1;
        for (limit = 1; limit <= ed; limit <<= 1) ++bit;
        A.resize(limit); B.resize(limit); rev.resize(limit);
        for (int i = 0; i < limit; ++i)    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << bit);
    }
    void ntt(vector<int>& P, int op) {
        for (int i = 0; i < limit; ++i) {
            if (i < rev[i])swap(P[i], P[rev[i]]);
        }
        for (int mid = 1; mid < limit; mid <<= 1) {
            int euler = qpow(3, (MOD - 1) / (mid << 1));
            if (op < 0)    euler = qpow(euler, MOD - 2);
            for (int i = 0, pos = mid << 1; i < limit; i += pos) {
                int wk = 1;
                for (int j = 0; j < mid; ++j, wk = mul(wk, euler)) {
                    int x = P[i + j], y = mul(wk, P[i + j + mid]);
                    P[i + j] = add(x, y), P[i + j + mid] = add(x, MOD - y);
                }
            }
        }
        if (op > 0)    return;
        int inv = qpow(limit, MOD - 2);
        for (int i = 0; i < limit; ++i)    P[i] = mul(P[i], inv);
    }
    void work() {
        for (int i = 0; i <= n; ++i) A[i] = i & 1 ? MOD - inv[i] : inv[i];
        for (int i = 0; i <= n; ++i) B[i] = mul(G[i], inv[i]);
        ntt(A, 1), ntt(B, 1);
        for (int i = 0; i < limit; ++i)    A[i] = mul(A[i], B[i]);
        ntt(A, -1);
    }
}using namespace NTT;


void init(int n) {
    jc[0] = 1;
    for (int i = 1; i <= n; ++i) {
        jc[i] = mul(jc[i - 1], i);
    }
    inv[n] = qpow(jc[n], MOD - 2);
    for (int i = n - 1; i >= 0; --i) {
        inv[i] = mul(inv[i + 1], i + 1);
    }
}
int C(int n, int m) {
    return 1ll * jc[n] * inv[n - m] % MOD * inv[m] % MOD;
}

int solve() {
    n = read(), a = read(), b = read();

    init(n);
    p = mul(a, qpow(b, MOD - 2)); // 没打中概率
    q = (1 - p + MOD) % MOD; // 打中概率

    int tmp_inv = mul(inv[n - 1], jc[n - 2]);
    for (int i = 0; i <= n; ++i) {
        G[i] = mul(qpow(add(q, mul(mul(p, i - 1), tmp_inv)), i), qpow(add(q, mul(mul(p, i), tmp_inv)), n - i));
    }
    init(), work();
    for (int i = n; i >= 0; --i) {
        print(1ll * C(n, i) * A[i] % MOD * jc[i] % MOD);
    }

    return 1;
}