题目链接
题目解法
很牛逼的概率题，参考了题解区
定义取到鬼牌，重新洗牌，为一轮
则 \(ans=E(\)轮数\()\times E(\)这一轮取到鬼牌的期望步数\()\)，轮数为在 \(S=\{1,...,n\}\) 之前取到鬼牌的次数
先计算 \(E(\)这一轮取到鬼牌的期望步数\()\)，这是比较好算的
考虑期望的线性性，即换角度考虑问题，我们假设会取完所有的牌，但第一次出现的鬼牌之后的牌不算步数，所以对于每个数字牌，前面没有鬼牌的概率显然为 \(\frac{1}{m+1}\)，所以取到鬼牌的期望次数为 \(\frac{n}{m+1}+1\)
再计算 \(E(\)轮数\()\)，这个也不太难算
取到在集合 \(S\) 中的数字牌对于答案是没有影响的，所以直接忽略
考虑当前剩余 \(i\) 张数字牌不在集合内，变到 \(i-1\) 张牌的期望轮数
在 \(m\) 张鬼牌，\(i\) 张数字牌中抽到数字牌的期望次数为 \(\frac{i+m}{m}\)，因为抽到数字牌不算轮数，所以期望轮数为 \(\frac{i}{m}\)
所以 \(E(\)轮数\()\) 即为 \(\sum\limits_{i=1}^n\frac{m}{i}+1\)
总结一下，答案为 \((\sum\limits_{i=1}^n\frac{m}{i}+1)\times (\frac{n}{m+1}+1)\)
时间复杂度 \(O(n)\)
个人感觉，这道题的难点在于想到定义轮数，即转化为 \(2\) 个期望次数，剩下的就比较套路
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
inline int read(){
int FF=0,RR=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
return FF*RR;
}
const int P=998244353,N=2000100;
int n,m,inv[N];
int qmi(int a,int b){
int res=1;
for(;b;b>>=1){ if(b&1) res=1ll*res*a%P;a=1ll*a*a%P;}
return res;
}
int main(){
n=read(),m=read();
inv[1]=1;
F(i,2,n) inv[i]=1ll*inv[P%i]*(P-P/i)%P;
int res=0;
F(i,1,n) res=(res+1ll*m*inv[i])%P;
int ans=(1ll*n*qmi(m+1,P-2)+1)%P*(res+1)%P;
printf("%d\n",ans);
return 0;
}