一、题目
注意一点:重新洗牌并不会导致集合 (S) 的变化。
二、解法
本题的关键是均匀随机洗牌,可以有一个 ( t observation):(S) 中具体有哪些数字是没有关系的,我们只需要知道 (S) 中有多少数字。因为所有数字是全等概率出现的,我们关系的就只有出现和不出现这两种状态了。
然后可以考虑用 (dp) 解决这个问题,直接 (dp) 时间有点难,因为有废牌((S) 中已经出现的牌)所以转移不动。
考虑用轮数来介导这个过程,因为答案可以表示成 (E(t_1+t_2...)),其中 (t_i) 表示第 (i) 轮的时间,可以拆成 (E(t_1)+E(t_2)...) 设 (E(x)) 表示期望要进行多少轮,那么答案是 (E(x)E(t)),其中 (E(t)) 表示每一轮的期望时间。
那么设 (f_i) 表示 (S) 中还缺少 (i) 张牌的期望轮数,这时候就可以忽略废牌了,考虑抽到的第一张有用牌是什么,如果是 ( t joker) 那么期望轮数 (+1),如果抽到了缺少的牌那么继续抽,显然抽到 ( t joker) 的概率是 (frac{m}{m+i}):
因为 (S) 满了之后还要抽到鬼才行,所以 (f_0=1),那么 (E(x)=1+sum_{i=1}^nfrac{m}{i})
现在算 (E(t)) 即可,我们考虑抽到鬼的时间,每张数字牌有 (frac{1}{m+1}) 的概率出现在第一张鬼前面,每张数字牌是独立的,那么做的总贡献是 (frac{n}{m+1}),还要算上抽到自己的时间,所以 (E(t)=1+frac{n}{m+1})
另一种方法是 (min-max) 反演,但是还是要以轮数为介导。
考虑给每个数字一个权值 (P(x)),表示加入 (x) 是第几轮。
设 (t) 表示一轮的期望时间,那么答案是 (tcdot E(max_{xin U}P(x))),直接上反演:
考虑求 (E(min_{xin T}P(x))),也就是一个集合中抽中第一张牌的轮数,每一轮抽出有用牌是 ( t joker) 的概率是 (frac{x}{x+m}),那么期望轮数可以表示成 (sum_{i=0}^{infty}(frac{x}{x+m})^i=frac{x+m}{x}),就是母函数的闭形式嘛,那么总答案是:
三、总结
核心原理是 (E(ab)=E(a)E(b)),所以期望不好算时要学会找介导量。
序列均匀随机有很多好的性质:比如元素等概率,顺序大小关系的概率会好算。
使用 (min-max) 反演的关键是定义权值,要求某些数全部出现是可以用,可以转化成某集合第一次出现数。
#include <cstdio>
#define int long long
const int MOD = 998244353;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,E,c;
int qkpow(int a,int b)
{
int r=1;
while(b>0)
{
if(b&1) r=r*a%MOD;
a=a*a%MOD;
b>>=1;
}
return r;
}
signed main()
{
n=read();m=read();
E=(n+m+1)*qkpow(m+1,MOD-2)%MOD;
for(int i=1;i<=n;i++)
c=(c+qkpow(i,MOD-2))%MOD;
c=(c*m+1)%MOD;
printf("%lld
",E*c%MOD);
}