花莲县网站建设_网站建设公司_VPS_seo优化

题目描述

考虑如下实验。有一副共 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; }