有(n+m)个球，(n)个球上写着互不相同的数字，(m)个球为空白。有个初始为空的集合(S)。将(n+m)个球随机排列。
从前往后操作，求期望操作多少次：
- 如果遇到一个数字(x)，在(S)中丢入(x)；在排列中删去(x)。
- 如果遇到空白：如果(|S|=n)，则退出；否则重新生成(n+m)个球的随机排列。
(n,mle 2*10^6)
好久没有在CF看见推式子题了啊。
一开始看错题意直到发现
原题求最后一个数出现的期望，首先很容易想到minmax容斥，枚举(T)算出(T)中的某个数第一次出现的期望。设(k=|T|)。
设生成函数(G(x))表示在做一轮（定义两次重排之间为一轮）的时候，操作(i)次退出的概率记在(x^i)上。
显然有：
[G_k(x)=sum_ifrac{inom{n-k}{i}i!(n+m-i-1)!m}{(n+m)!}x^{i+1}
]
设(F(x))表示这道题的概率生成函数，有：
(F(x)=sum_{k=1}^ninom{n}{k}(-1)^{k-1}frac{G_0(x)-G_k(x)}{1-G_k(x)}\=sum_{k=1}^ninom{n}{k}(-1)^{k}(frac{1-G_0(x)}{1-G_k(x)}-1)\=(sum_{k=1}^ninom{n}{k}(-1)^{k}frac{1}{1-G_k(x)})(1-G_0(x))+1)
根据概率生成函数的基本性质，有(E(x)=F'(1))。推一波式子之后得到：（注意推导过程中有用到(G_0(1)=1)）
[F'(1)=-sum_{k=1}^{n}inom{n}{k}(-1)^kfrac{1}{1-G_k(1)}G_0'(1)
]
(G_0'(1))可以线性求。
(G_k(1))考虑组合意义：原来是随机排列满足第一个空白之前，都是在(T)之外(n-k)个数字的概率。不妨转化成：(n-k)个不同球和(m+k)个不同标号的球插在一起，(n-k)个球内部顺序任意排列，(m+k)个球除第一个必须是空白的之外其它任意排列。于是有(G_k(1)=frac{inom{n-k}{n+m}(n-k)!(m+k-1)!m}{(n+m)!})。可以(O(1))求。
于是时间复杂度是线性的。
using namespace std;
#include <bits/stdc++.h>
#define N 2000005
#define ll long long
#define mo 998244353
ll qpow(ll x,ll y=mo-2){
ll r=1;
for (;y;y>>=1,x=x*x%mo)
if (y&1)
r=r*x%mo;
return r;
}
int n,m;
ll fac[N*2],ifac[N*2];
void initC(int n){
fac[0]=1;
for (int i=1;i<=n;++i)
fac[i]=fac[i-1]*i%mo;
ifac[n]=qpow(fac[n]);
for (int i=n-1;i>=0;--i)
ifac[i]=ifac[i+1]*(i+1)%mo;
}
ll C(int m,int n){return fac[m]*ifac[n]%mo*ifac[m-n]%mo;}
ll iC(int m,int n){return ifac[m]*fac[n]%mo*fac[m-n]%mo;}
ll ans;
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
initC(n+m);
ll p=0;
for (int i=0;i<=n;++i)
(p+=C(n,i)*fac[i]%mo*fac[n+m-i-1]%mo*ifac[n+m]%mo*(i+1))%=mo;
p=p*m%mo;
ll s=0;
for (int k=1;k<=n;++k){
ll t=0;
// for (int i=0;i<=n-k;++i)
// (t+=C(n-k,i)*fac[i]%mo*fac[n+m-i-1]%mo*ifac[n+m])%=mo;
// t=t*m%mo;
t=C(n+m,n-k)*fac[n-k]%mo*fac[m+k-1]%mo*m%mo*ifac[n+m]%mo;
(s+=(k&1?-1:1)*C(n,k)*qpow(1-t))%=mo;
}
ll ans=(-s*p%mo+mo)%mo;
printf("%lld
",ans);
return 0;
}