2021牛客暑期多校训练营4 B、Sample Game

题目大意

你有一个随机数生成器，他会随机生成 $1$ 到 $n(1\le n\le 100)$ 之间某个数，生成 $i$ 的概率为 $p_i$ 。

现在分为大体 $3$ 步操作：

随机生成一个 $x$ 。
如果这个 $x$ 是已经生成的数中最大的，返回步骤一继续生成新的数，否则进入步骤三
游戏结束，本局游戏的得分为生成序列的长度的平方 $y^2$ 。

现在要你求出这局游戏的得分期望 $E(y^2)$ 。

Solution

考点：期望dp

$E(y^2)$ 这个期望不是很好求，我们优先考虑求出 $E(y)$ 。

我们假设 $f_x$ 是随机到 $x$ 后还能进行的期望抽取次数，那么我们知道 $E(y)=f_y+1$ ，那么我们把之后的抽取分为 $(1\to (x-1)),x,((x+1)\to n)$ 这三类，可以知道，抽到 $1\to (x-1)$ 之后就无法进行了这时候的期望次数就是 $\sum\limits_{i=1}^{x-1}p_i*1$ ，如果抽到了相同的数 $x$ ，这时候他带来的期望次数就是 $p_x(1+f_x)$ ，如果抽到了 $((x+1)\to n)$ ，他们的期望次数是 $\sum\limits_{i=x+1}^n p_i(1+f_i)$ 。

我们总结上面三种情况就可以得到下面式子：

$f_x=\sum\limits_{i=1}^{x-1}p_i+p_x(1+f_x)+\sum\limits_{i=x+1}^np_i(1+f_i)$

进行移相化简，并且知道 $\sum\limits_{i=1}^np_i = 1$ 之后我们可以得到这样的最终式子。

$\displaystyle f_x=\frac{1+\sum\limits_{i=x+1}^np_if_i}{1-p_x}$

看出这个是一个倒序的递推式，倒序的处理即可求到 $f_x$ 的全部值，也就是 $E(y)$ 。

接下来题目要求的是 $E(y^2)$ 的期望，在概率论中，有这样的式子 $D(y)=E(y^2)-E(y)^2$ ，也就是方差等于平方的期望减掉期望的平方，所以我们不能把 $E(y^2)$ 和 $E(y)^2$ 划等号。

和求 $f_x$ 同理，我们假设 $g_x$ 代表随机到 $x$ 后游戏的期望得分也就是剩余回合数的平方，那么我们知道 $E(y^2)=(f_y+1)^2=f_y^2+2f_y+1=g_y+2f_y+1$ 。

和 $f_x$ 同样的对下次抽取的数字以 $x$ 分三类情况，可以得到 $g_x$ 的递推式。

$\displaystyle g_x=\sum\limits_{i=1}^{x-1}p_i+p_x(g_x+2f_x+1)+\sum\limits_{i=x+1}^np_i(g_i+2f_i+1)\\g_x=\frac{1+2p_xf_x+\sum\limits_{i=x+1}^np_i(g_i+2f_i)}{1-p_x}$

同样的倒序递推就可以得到 $g_x$ 全部的值。

下面套用我们求解 $ans =\sum\limits_{i=1}^n p_i* E(i^2)=\sum\limits_{i=1}^np_i(g_i+2f_i+1)=1+\sum\limits_{i=1}^np_i(g_i+2f_i)$

套用快速幂和费马小定理求解逆元就出来答案了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op)    putchar(op); return; }    char F[40]; ll tmp = x > 0 ? x : -x;    if (x < 0)putchar('-');    int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';        tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]);    if (op)    putchar(op); }
ll qpow(ll a, ll b) { ll ans = 1;    while (b) { if (b & 1)    ans *= a;        b >>= 1;        a *= a; }    return ans; }    ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
const int MOD = 998244353;

const int N = 100 + 7;
ll n, m;
int w[N], p[N], inv[N];
int f[N], g[N];

inline int add(int a, int b) {
    if (a + b >= MOD)    return a + b - MOD;
    return a + b;
}

int solve() {
    n = read();
    int sum = 0;
    for (int i = 1; i <= n; ++i) {
        w[i] = read();
        sum += w[i];
    }
    int tmp = qpow(sum % MOD, MOD - 2, MOD);
    for (int i = 1; i <= n; ++i) {
        p[i] = w[i] * tmp % MOD;
        inv[i] = qpow((1 - p[i] + MOD) % MOD, MOD - 2, MOD);
    }
    sum = 0;
    for (int i = n; i >= 1; --i) {
        f[i] = add(1, sum) * inv[i] % MOD;
        sum = add(sum, p[i] * f[i] % MOD);
    }
    sum = 0;
    for (int i = n; i >= 1; --i) {
        g[i] = add(add(1, 2 * p[i] * f[i] % MOD), sum) * inv[i] % MOD;
        sum = add(sum, p[i] * add(g[i], 2 * f[i] % MOD) % MOD);
    }
    int res = 0;
    for (int i = 1; i <= n; ++i) {
        res = add(res, add(g[i], (2 * f[i] + 1) % MOD) * p[i] % MOD);
    }
    print(res);

    return 1;
}

signed main() {
    //int T = read(); for (int i = 1; i <= T; ++i)
    {
        solve();
        //cout << (solve() ? "YES" : "NO") << endl;
    }
    return 0;
}