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