UOJ514 「UR#19」通用测评号
考场上推出来了式子，手算样例算错，然后扔了，赛后发现算错，重算了一遍发现是对的。
「你每次会等概率随机选一个没有满的燃料舱」
考虑也可以选择满了的燃料舱，这不会影响答案
这样每次选每个燃料舱的概率都是一样的。
考虑枚举最后一个到b的燃料舱，再枚举一个满了的燃料舱计算方案数
记\(S(i)=\frac{\frac{x}{n}^i}{i!}\)
满了的方案数的指数生成函数为\(e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i)\)
其它的不一定满，方案数为\(e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i)\)
最后这个燃料舱的第b次操作一定在最后，所以\(\cdot \frac{1}{n}\)然后只考虑前面的操作\(S(b-1)\)
那么满足条件的概率的指数生成函数为\((n-1)(e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i))(e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i))^{n-2}S(b-1)\)
设生成函数为\(F(x)=\sum \frac{a_ix^i}{i!}\)，则设\(G(x)=\sum a_ix^i\)，答案为\(G(1)\)，也就是\(\sum a_i\)。
考虑计算这个函数。
由于exp很难处理，考虑把式子展开成\(\sum e^{\frac{ix}{n}}F_i(x)\)的形式。
先考虑\((e^{\frac{x}{n}}-\sum_{i=0}^{b-1}S(i))^{n-2}\)，则答案是\(\sum_{i=0}^{n-2}\binom{n-2}{i}e^{\frac{ix}{n}}(-\sum_{i=0}^{b-1}S(i))^{n-2-i}\)，
乘上\(e^{\frac{x}{n}}-\sum_{i=0}^{a-1}S(i)\)也类似。
由于得到的多项式次数\(\lt
na\)，所以可以先DFT，乘完再IDFT。
这一部分的复杂度是\(O(n^2a\log(na))\)，也就是\(n\)次IDFT的复杂度。
考虑计算答案。生成函数可以拆成\(c\cdot e^{ax}\frac{x^b}{b!}\)的形式，对于每个这种式子计算答案。
\(e^{ax}\frac{x^b}{b!}=\sum_{i=0}^{\infty}\frac{a^ix^{i+b}}{i!b!}=\sum_{i=0}^{\infty}a^{i}\binom{i+b}{i}\frac{x^{i+b}}{(i+b)!}\)
那么得到的普通型生成函数为\(\sum_{i=0}^{\infty}\binom{i+b}{i}a^ix^{i+b}=\frac{x^b}{(1-ax)^{b+1}}\)。
于是做完了。
代码（已define int long long）：
const int p=998244353,G=114514;
int inv[62505],fac[62505],invf[62505],pw[62505];
int cnt[255],n,a,b,s,k,ans,w=1;
int f[255][65537],iN,N;
int fpm(int a,int b){
int c=1;for(;b;b>>=1,a=a*a%p)if(b&1)c=c*a%p;
return c;
}
int f1[65537],f2[65537];
int _w[1<<17|5],rev[1<<16|5];
int Sum(int a,int b){return (a+=b)>=p?a-p:a;}
void dft(int *a){
for(int i=0;i<N;++i)if(i>rev[i])swap(a[i],a[rev[i]]);
for(int i=1;i<N;i<<=1){
for(int j=0;j<N;j+=i+i){
for(int k=0;k<i;++k){
int u=a[j+k],v=a[j+k+i]*_w[k+i]%p;
a[j+k]=Sum(u,v);
a[j+k+i]=Sum(u,p-v);
}
}
}
}
void idft(int *a){
reverse(a+1,a+N);
dft(a);
for(int i=0;i<N;++i)a[i]=a[i]*iN%p;
}
signed main(){
#ifdef QAQAutoMaton
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
read(n,a,b);
int w=(a-1)+(n-1)*b;
fac[0]=fac[1]=inv[1]=invf[0]=invf[1]=1;
for(int i=2;i<=w;++i){
fac[i]=fac[i-1]*i%p;
inv[i]=(p-p/i)*inv[p%i]%p;
invf[i]=inv[i]*invf[i-1]%p;
}
int in=inv[n];
pw[0]=1;
for(int i=1;i<=w;++i){
pw[i]=pw[i-1]*in%p;
}
N=1;
while(N<=w)N<<=1;
for(int i=1;i<N;i<<=1){
int ww=fpm(G,(p+1)/(i<<1)),w=1;
for(int j=0;j<i;++j){
_w[i+j]=w;
w=w*ww%p;
}
}
for(int i=1;i<N;++i){
rev[i]=(rev[i>>1]>>1)|((i&1)*(N>>1));
}
iN=fpm(N,p-2);
for(int i=0;i<b;++i)f1[i]=p-pw[i]*invf[i]%p;
for(int i=0;i<a;++i)f2[i]=p-pw[i]*invf[i]%p;
dft(f1);dft(f2);
for(int i=0;i<N;++i)f[0][i]=1;
for(int i=1;i<=n-2;++i){
for(int j=0;j<N;++j)f[i][j]=f[i-1][j]*f1[j]%p;
}
for(int i=0;i<=n-2;++i){
int C=fac[n-2]*invf[i]%p*invf[n-2-i]%p;
for(int j=0;j<N;++j)f[i][j]=f[i][j]*C%p;
}
for(int i=n-2;~i;--i){
for(int j=0;j<N;++j)f[i+1][j]=(f[i+1][j]+f[i][j]*f2[j])%p;
}
for(int i=0;i<=n-1;++i){
idft(f[i]);
}
for(int i=0;i<=n-1;++i){
int wx=n*inv[i+1]%p,cur=invf[b-1]*pw[b-1]%p;
for(int j=0;j<b-1;++j)cur=cur*wx%p;
for(int j=0;j<=w;++j){
cur=cur*wx%p;
ans=(ans+f[i][j]*fac[j+b-1]%p*cur)%p;
}
}
write(ans*(n-1)%p,'\n');
return 0;
}