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

Sample Game

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

题目大意

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

输入为 个数

思路

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

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

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

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

,时间复杂度 ,最后 代入求

代码

#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;
}
牛客暑期多校训练营题解 文章被收录于专栏

收集牛客暑期多校训练营的题解

全部评论

相关推荐

把球:这个听过,你加了就会发现是字节的hr
点赞 评论 收藏
分享
想要成为offer实力者:亚信实习能干这些?确定不是包装
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务