XV.[HEOI2016/TJOI2016]求和
题意：求一个东西
(LARGEsumlimits_{i=0}^nsumlimits_{j=0}^iS_i^j*2^j*j!)
其中(S_i^j)为第二类斯特林数，递推公式为(S_n^m=S_{n-1}^{m-1}+m*S_{n-1}^m)。
我们终于可以像莫反一样，开始喜闻乐见地推式子辣！
首先，就让我这个半小时前还在看斯特林数的blog的蒟蒻暂且口胡一下第二类斯特林数的意义吧！
(S_n^m)，意为将(n)个球放入(m)个集合（无序！不能隔板法！），且每个集合都非空的方案数。
我们有递推式(S_n^m=S_{n-1}^{m-1}+m*S_{n-1}^m)，可以这样想：如果第(n)个球独立放入一个集合，方案数为(S_{n-1}^{m-1})；否则，可以把它扔进任何一个集合中，共有(m*S_{n-1}^m)种方案。
当然也有通项公式：
(LARGE S_n^m=dfrac{sumlimits_{i=0}^m(-1)^iC_m^i(m-i)^n}{m!})
再来口胡一下证明：
我们这个(sumlimits_{i=0}^m)相当于枚举这(m)个集合中空集合的数量有(i)个。我们从共(m)个集合中选择(i)个空置，共有(C_m^i)种方案；((-1)^i)是容斥原理的结果，我们反正这么瞎加加减减就能把所有有空集合的方案全都容斥掉。((m-i)^n)因为每个元素可以扔进(m-i)个非空集合中的任何一个，共扔(n)次。显然，这么扔肯定是有序的，不满足集合无序的要求，故分母上有个(m!)。
回忆一下，(C_m^i=dfrac{m!}{i!(m-i)!})，我们把它带进去，得到：
(LARGE S_n^m=sumlimits_{i=0}^mdfrac{(-1)^i(m-i)^n}{i!(m-i)!})
欧拉！我们就可以把(S_i^j)的定义带回原式中了。
原式：
(LARGEsumlimits_{i=0}^nsumlimits_{j=0}^iS_i^j*2^j*j!)
首先，当((i<j))时，我们有(S_i^j=0)。很显然，因为此时必有空集合存在。因此，我们可以将(sumlimits_{j=1}^i)改为(sumlimits_{j=1}^n)。得到：
(LARGEsumlimits_{i=0}^nsumlimits_{j=0}^nS_i^j*2^j*j!)
改变枚举顺序，先枚举(j)，并把只与(j)有关的东西移出去。
(LARGEsumlimits_{j=0}^n2^j*j!sumlimits_{i=0}^nS_i^j)
(S_i^j)通项公式代进去：
(LARGEsumlimits_{j=0}^n2^j*j!sumlimits_{i=0}^nsumlimits_{k=0}^jdfrac{(-1)^k(j-k)^i}{k!(j-k)!})
发现这个(i)只与((j-k)^i)有关，不如就在那边求和，得到
(LARGEsumlimits_{j=0}^n2^j*j!sumlimits_{k=0}^jdfrac{(-1)^kBigg(sumlimits_{i=0}^n(j-k)^iBigg)}{k!(j-k)!})
把后面那一大坨拆成与(k)有关的和与(j-k)有关的：
(LARGEsumlimits_{j=0}^n2^j*j!sumlimits_{k=0}^jBigg(dfrac{(-1)^k}{k!}Bigg)Bigg(dfrac{sumlimits_{i=0}^n(j-k)^i}{(j-k)!}Bigg))
发现后面是一个卷积的形式。令(f(i)=dfrac{(-1)^i}{i!})，(g(i)=dfrac{sumlimits_{k=0}^ni^k}{i!})
利用等比数列求和的公式，得到(g(i)=dfrac{i^{n+1}-1}{(i-1)i!})。
注意！在这么转换之后，我们要注意到特例：(i=0)和(i=1)。在新式子中，会得到奇奇怪怪的结果。直接代入原式子，得到(g(0)=1)和(g(1)=n+1)，记得特判一下！
设(h=f*g)，则我们得到：
(LARGEsumlimits_{j=0}^n2^j*j!*h(j))
问题来了，这个(2^j*j!)是干什么的？
误导你的！自始至终它都一直在那里呆着。
出题人竟如此阴险残暴
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int G=3;
int n,f[500100],g[500100],lim=1,lg,invlim,rev[500100],ans;
int ksm(int x,int y){
int res=1;
for(;y;x=(1ll*x*x)%mod,y>>=1)if(y&1)res=(1ll*res*x)%mod;
return res;
}
void NTT(int *a,int tp){
for(int i=0;i<lim;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int md=1;md<lim;md<<=1){
int rt=ksm(G,(mod-1)/(md<<1));
if(tp==-1)rt=ksm(rt,mod-2);
for(int stp=md<<1,pos=0;pos<lim;pos+=stp){
int w=1;
for(int i=0;i<md;i++,w=(1ll*w*rt)%mod){
int x=a[pos+i],y=(1ll*w*a[pos+md+i])%mod;
a[pos+i]=(x+y)%mod;
a[pos+md+i]=(x-y+mod)%mod;
}
}
}
if(tp==-1)for(int i=0;i<lim;i++)a[i]=(1ll*a[i]*invlim)%mod;
}
int main(){
scanf("%d",&n);
for(int i=0,fac=1,invfac;i<=n;i++,fac=(1ll*fac*i)%mod){
invfac=ksm(fac,mod-2);
f[i]=(i&1?(mod-invfac)%mod:invfac);
if(i==0)g[i]=1;
else if(i==1)g[i]=n+1;
else g[i]=1ll*(ksm(i,n+1)-1+mod)%mod*ksm(i-1,mod-2)%mod*invfac%mod;
}
while(lim<=2*n+1)lim<<=1,lg++;
invlim=ksm(lim,mod-2);
for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
NTT(f,1),NTT(g,1);
for(int i=0;i<lim;i++)f[i]=(1ll*f[i]*g[i])%mod;
NTT(f,-1);
for(int i=0,fac=1,bin=1;i<=n;i++,fac=(1ll*fac*i)%mod,bin=(bin<<1)%mod)ans=(1ll*fac*bin%mod*f[i]%mod+ans)%mod;
printf("%lld
",ans);
return 0;
}