2021牛客多校4 B Sample Game

题目描述

https://ac.nowcoder.com/acm/contest/11255/B

简要题意：给定 $n$ 和 $[1,n]$ 中生成每个数的概率 $p_i$，现在开始随机生成 $[1,n]$ 的数，若生成的数不是已经生成的数的最大值，那么停止生成，最终得分是生成的数的个数的平方，求期望得分

$n\le 100$

Solution

我们考虑概率生成函数 $F(x)=\sum_{i=0}^{\infty}\Pr(X\ge i)x^i$​，随机变量 $X$ 表示生成的数的个数

那么我们发现 $F(x)=\prod_{i=1}^n\frac{1}{1-p_ix}$​，原因的话，我们考虑枚举所有生成了 $k$​ 个数的情况，因为这 $k$​ 个数的生成只有一种顺序，所以可以看成集合

考虑将我们要求的东西转换成与 $F(x)$ 有关的式子：

$$\begin{aligned} \sum_{i=0}^{\infty}i^2\Pr(X=i)x^i&=\sum_{i=0}^{\infty}i^2(\Pr(X\ge i)-\Pr(X\ge i+1))x^i\\ &=\sum_{i=0}^\infty i^2\Pr(X\ge i)x^i-\sum_{i=0}^\infty i^2\Pr(X\ge i+1)x^i\\ &=\sum_{i=0}^\infty(2i+1)\Pr(X\ge i)x^i\\ &=2F'(x)+F(x) \end{aligned}$$

那么答案就是 $2F’(1)+F(1)$，容易得到 $F’(x)=F(x)\sum_{i=1}^n\frac{p_i}{1-p_ix}$

时间复杂度 $O(n)$

#include <iostream>
#define maxn 1000010
#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;
}

int n;

ll P[maxn], f[maxn], g[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; ll sum = 0, inv, ans = 1; 
    for (int i = 1; i <= n; ++i) cin >> P[i], sum += P[i]; inv = pow_mod(sum, p - 2);
    for (int i = 1; i <= n; ++i) P[i] = P[i] * pow_mod(sum, p - 2) % p;
    for (int i = 1; i <= n; ++i) ans = ans * pow_mod(1 - P[i], p - 2) % p;
    sum = 0;
    for (int i = 1; i <= n; ++i) sum = (sum + P[i] * pow_mod(1 - P[i], p - 2)) % p;
    ans = (ans + 2 * ans * sum) % p;
    cout << (ans + p) % p << "\n";
    return 0; 
}