Problem - 7330

题目大意：有n次游戏，每次游戏有a/b的概率获胜，且相互独立，如果当前赢了cnt次游戏，那么这次游戏会赢得的分数，问最后得分的期望

1<=n<=1e6;1<=m,a<=b<998244353

思路：因为每次事件相互独立，且只有输和赢两种结果，所以是一个二项分布，但每次事件的得分不同，所以要对赢几次分别求概率和得分相乘，最后再加起来就是总的期望，得分因为是递增的，所以用一个前缀和维护，每多赢一次，sum就加上赢得次数i的m次方。

概率就是二项分布的概率，C(i,n) *，分母固定为，我们只需要维护两个分子，分子1初始化为a，分子而初始化为，每次求完一次，分子1*a，分子2除以b-a。

然后注意到本题数据范围是1e6，且可能有10组1e6，如果O(nlogn)的话，超过1e8级别，比较极限，所以对于组合数也要预处理，即先预处理好1~1e6的阶乘数组和阶乘逆元数组，之后C(a,b)即b!/(a!(b-a)!)就可以O(1)求出

//#include<__msvc_all_public_headers.hpp>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const int N = 1e6 + 5;
ll inv[N], fac[N];
ll C(ll x, ll y)
{//C(x,y)=y!/((y-x)!x!)return fac[y] * inv[x] % MOD * inv[y - x] % MOD;
}
ll qpow(ll a, ll b)
{//快速幂ll ret = 1;while (b){if (b & 1){ret = ret * a % MOD;}a = a * a % MOD;b >>= 1;}return ret;
}
int main()
{int t;cin >> t;fac[0] = 1;inv[0] = 1;for (ll i = 1; i <= 1000000; i++){//预处理阶乘和阶乘逆元fac[i] = (fac[i - 1] * i) % MOD;inv[i] = qpow(fac[i], MOD - 2);}while (t--){int n, m;ll a, b;cin >> n >> m >> a >> b;ll sum = 0;ll ans = 0;ll temp1 = a;//分子1ll temp2 = qpow(b-a, n - 1);//分子2ll temp3 = qpow(qpow(b, n), MOD - 2);//分母ll temp4 = qpow(b - a, MOD - 2);//分子2每次*的逆元for (ll i = 1; i <= n; i++){//枚举n次里面赢几次的期望sum = (sum + qpow(i, m)) % MOD;//得分ll p = temp1 * temp2 % MOD * temp3 % MOD * C(i, n) % MOD;//概率ans = (ans + p * sum % MOD) % MOD;//期望和temp2 = temp2 * temp4 % MOD;temp1 = temp1 * a % MOD;}cout << ans << endl;}return 0;
}