《CF1278F Cards》
题目描述
考虑如下实验。有一副共 m 张牌的牌堆，且恰好有一张是小丑牌。你将进行 n 次如下操作：将牌堆洗牌，从牌堆顶端抽出一张牌，查看后再放回牌堆。
设 x 表示在本次实验中你抽到小丑牌的次数。假设每次洗牌后，所有 m! 种牌的排列都是等概率的，求 xk 的期望值是多少？请将答案对 998244353 取模后输出。
输入格式
一行包含三个整数 n、m 和 k（1≤n,m<998244353，1≤k≤5000）。
输出格式
输出一个整数，表示 xk 的期望值对 998244353 取模的结果（答案总可以表示为最简分数 ba，其中 bmod998244353=0；你需要输出 a⋅b−1mod998244353）。
显示翻译
题意翻译
输入输出样例
输入 #1复制
1 1 1
输出 #1复制
1
输入 #2复制
1 1 5000
输出 #2复制
1
输入 #3复制
2 2 2
输出 #3复制
499122178
输入 #4复制
998244352 1337 5000
输出 #4复制
326459680
说明/提示
由 ChatGPT 4.1 翻译
代码实现：
#include<bits/stdc++.h> #define ll long long #define rg register using namespace std; const ll mod=998244353; inline ll rd() { register ll s=0,f=0; register char ch=getchar(); while(!isdigit(ch)) f|=(ch=='-'),ch=getchar(); while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar(); return f?-s:s; } ll n,m,k,dp[5001][5001],res,iv; inline ll qp(ll a,ll b) { ll ret=1; for(ll t=b; t; t>>=1,a=(a*a)%mod) { if(t&1)ret=(ret*a)%mod; } return ret; } inline ll cal(int x) { ll ret=1; for(int i=1; i<=x; i++)ret=(ret*(n-i+1))%mod; return ret; } int main() { n=rd(),m=rd(),k=rd(),iv=qp(m,mod-2); for(int i=0; i<=k; i++)dp[i][i]=1; for(int i=2; i<=k; i++) { for(int j=1; j<i; j++)dp[i][j]=(dp[i-1][j]*j+dp[i-1][j-1])%mod; } for(int i=0; i<=k; i++) res=(res+dp[k][i]*cal(i)%mod*qp(iv,i)%mod)%mod; printf("%lld\n",res); return 0; }