loj2541 「PKUWC2018」猎人杀

题目传送门

传送门


分析

好题好题。

因为每轮概率都会改变,有点不好做。我们可以令每轮选到每个人的概率都不变,也就是说可能会再次选到死人,选到死人我们就忽略这一轮。

题目要求$1$号最后死,也就是说$2$到$n$每个人都要比$1$先死。对于这种同时满足多个限制的问题,可以用容斥原理,变成强行令某几个限制不满足。对于此题,我们枚举比$1$后死的人,设选了$k$个人,选中的$w_i$之和为$S$,$\sum_{i=1}^{n}w_i=A$,则

$$ans=\sum[(-1)^t\cdot \sum_{i\ge 0}(1-\frac{w_1+S}{A})^i\cdot \frac{w_1}{A}]$$

中间那个$\sum_{i\ge 0}(1-\frac{w_1+S}{A})^i$用等比数列求和可知收敛于$\frac{A}{w_1+S}$,则

$$ans=\sum[(-1)^t\cdot \frac{w_1}{w_1+S}]$$

显然不能$2^n$枚举所有选人方案,但发现$S$的上限不大,如果预处理出每个$S$的容斥系数之和,就可以$O(S)$算答案。

对于每个猎人,构造生成函数$-x^{w_i}+1$,把所有人的函数卷积起来即可。可以用分治+NTT求解,复杂度$O(n\log^2 n)$。

代码

#include <bits/stdc++.h>
using std::vector;
typedef long long ll;

const int N = 1e5+50;
const int P = 998244353;

int qPow(int x, int k) {
    int rtn = 1;
    for (; k; k >>= 1, x = (ll)x * x % P)
        if (k & 1) rtn = (ll)rtn * x % P;
    return rtn;
}

namespace NTT {
    const int G = 3;

    int n, rev[N<<2];
    int ta[N<<2], tb[N<<2];

    void init(int m) {
        int len = 0;
        for (n = 1; n < m; n <<= 1, len++);
        for (int i = 1; i < n; i++)
            rev[i] = rev[i>>1] >> 1 | (i&1) << len-1;
    }

    void NTT(int f[], int sgn) {
        for (int i = 0; i < n; i++)
            if (rev[i] > i) std::swap(f[i], f[rev[i]]);
        for (int i = 1; i < n; i <<= 1) {
            int gn = qPow(G, (P-1)/(2*i));
            if (sgn == -1) gn = qPow(gn, P-2);
            for (int j = 0; j < n; j += i << 1) {
                int g = 1;
                for (int k = 0; k < i; k++, g = (ll)g * gn % P) {
                    int x = f[j+k], y = (ll)g * f[j+i+k] % P;
                    f[j+k] = (x + y) % P;
                    f[j+i+k] = (x - y) % P;
                }
            }
        }
        if (sgn == -1) {
            int invn = qPow(n, P-2);
            for (int i = 0; i < n; i++)
                f[i] = (ll)f[i] * invn % P;
        }
        for (int i = 0; i < n; i++)
            f[i] = (f[i] + P) % P;
    }

    void mul(vector<int> &a, vector<int> &b, vector<int> &res) {
        int la = a.size(), lb = b.size();
        int m = la + lb - 1;
        init(m);
        for (int i = 0; i < n; i++)
            ta[i] = tb[i] = 0; 
        for (int i = 0; i < la; i++)
            ta[i] = a[i];
        for (int i = 0; i < lb; i++)
            tb[i] = b[i];
        NTT(ta, 1);
        NTT(tb, 1);
        for (int i = 0; i < n; i++)
            ta[i] = (ll)ta[i] * tb[i] % P;
        NTT(ta, -1);
        res.resize(m);
        for (int i = 0; i < m; i++)
            res[i] = ta[i];
    }
}

int n, w[N];
vector<int> t[20];

void solve(int l, int r, int dep) {
    if (l == r) {
        t[dep].clear();
        t[dep].resize(w[l]+1);
        t[dep][0] = 1;
        t[dep][w[l]] = P-1;
        return;
    }
    int mid = l + r >> 1;
    solve(l, mid, dep+1);
    t[dep] = t[dep+1];
    solve(mid+1, r, dep+1);
    NTT::mul(t[dep], t[dep+1], t[dep]);
}

int main() {
    scanf("%d", &n);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
        if (i > 1) tot += w[i];
    }
    solve(2, n, 0);
    int ans = 0;
    for (int i = 0; i <= tot; i++)
        ans = (ans + (ll)t[0][i] * w[1] % P * qPow(i + w[1], P-2)) % P;
    ans = (ans + P) % P;
    printf("%d\n", ans);
    return 0;
}


转载请注明出处。


评论列表,共 0 条评论

    暂无评论

发表评论