2021牛客暑期多校4 B.Sample Game

题目大意

玩一场游戏，每一轮在 中随机生成一个整数 ，生成 的概率为 。若 不小于之前生成的任何数，则游戏继续并进入下一轮，否则游戏结束。假如说最后游戏共进行了 轮，则游戏的得分为 。求游戏分数的期望值 ，答案 输出。

输入为 个数 ，。

思路

游戏生成的数字序列一定是类似 ，即 的数字由小到大依次产生，每个数字出现的次数为 。

构造母函数 ，对于每一项 ，指数 表示数字 出现的次数， 就是 连续出现 次的概率。每一个数的出现次数都对应多项式 ，将这 个多项式进行卷积运算，即为 。卷积的结果为 ， 为生成序列的长度，系数 自然是生成长度为 的非递减序列的概率。仔细思考， 同时也是游戏进行轮次超过 次的概率，即 ；因为游戏已经进行了 轮，且可以继续进行，游戏要进行超过 轮等价于生成长度为 的非递减序列。

根据数学期望的定义，枚举最后游戏的轮次 。

根据 可以发现，。我们需要用 来求 和 。首先将 化为其封闭形式，即 。将 带入 ，容易得到 。将 两边取自然对数，；两边对 求导，；将 带入，得 。将 代入，并记 ，有 ，。

求 和 ，时间复杂度 ，最后 代入求 。

代码

#include<iostream>
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int MAX_SIZE = 105;
int n, w[MAX_SIZE];
ll QuickPower(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
int main()
{
    cin >> n;
    int sum = 0;
    for (int i = 1;i <= n;i++)
    {
        cin >> w[i];
        sum += w[i];
    }
    // 求 f(1)
    int a = 1;
    for (int i = 1;i <= n;i++)
    {
        a = 1ll * a * sum % MOD * QuickPower(sum - w[i], MOD - 2) % MOD;
    }
    // 求 f'(1)
    int b = 0;
    for (int i = 1;i <= n;i++)
    {
        b = (b + 1ll * w[i] * QuickPower(sum - w[i], MOD - 2) % MOD) % MOD;
    }
    b = 1ll * b * a % MOD;
    // 输出答案
    cout << (2ll * b % MOD + a) % MOD << endl;
    return 0;
}