题意：求给定n，求这个式子%一个NTT模数的值。  $ f(n) = \sum\limits_{i = 0}^n {\sum\limits_{j = 0}^i {s(i,j)*{2^j}*j!} } $ 其中S（i，j）为第二类斯特林数。

题解：首先根据第二类斯特林数的定义，我们可以把第二个sigma上界变成n（这里很关键，就是因为这个没看出来导致没推出卷积形式。。）

根据第二类斯特林数的公式，式子可以写成 

$ \begin{array}{l}f(n) = \sum\limits_{i = 0}^n {\sum\limits_{j = 0}^n {\sum\limits_{k = 0}^j {

{

{( - 1)}^k}*\frac{

{

{

{(j - k)}^i}}}{

{k!(j - k)!}}} {2^j}*j!} } \\\end{array} $

再把i的sigma丢到后面去 $ \begin{array}{l}f(n) = \sum\limits_{j = 0}^n {\sum\limits_{k = 0}^j {

{

{( - 1)}^k}*\frac{

{\sum\limits_{i = 0}^{\rm{n}} {

{

{(j - k)}^i}} }}{

{k!(j - k)!}}} {2^j}*j!} \\\end{array} $

或者写成这样更显然一点 $ \begin{array}{*{20}{l}}{f(n) = \sum\limits_{j = 0}^n {

{2^j}*j!\sum\limits_{k = 0}^j {\frac{

{

{

{( - 1)}^k}}}{

{

{\rm{k!}}}}*\frac{

{\sum\limits_{i = 0}^{\rm{n}} {

{

{(j - k)}^i}} }}{

{(j - k)!}}} } }\end{array} $

这个式子就是个卷积，直接NTT咯。

这道题有些坑点，首先对于卷积那一部分里我们要弄一个等比数列求和，这里公比为1的时候要注意一下（还记得等比数列求和公式要分类讨论吗？）

然后还有对于第0项的讨论。这些都要注意。

1 #include
     
       2 using namespace std; 3 #define LL long long 4 #define mod 998244353 5 #define N 400005 6 #define G 3 7  8 inline LL read(){ 9     int x=0,f=1; char a=getchar();10     while(a<'0' || a>'9') {
   if(a=='-') f=-1; a=getchar();}11     while(a>='0' && a<='9') x=x*10+a-'0',a=getchar();12     return x*f;13 }14 15 int n,fac[N],nfac[N],two[N],a[N],b[N],f[N],ans;16 17 inline int fpow(int x,int k){18     int ret=1;19     while(k){20         if(k&1) ret=1LL*ret*x%mod;21         k>>=1; x=1LL*x*x%mod;22     }23     return ret;24 }25 26 namespace NTT{27     int rev[N],wn[30];28     29     inline void getwn(){
   for(int i=1,t=2;i<20;i++,t<<=1) wn[i]=fpow(G,(mod-1)/t);}30     31     inline void ntt(int x[],int len,int f){32         for(int i=1;i<=len;i++) if(i
      
       >1]>>1|(i&1?t:0);55         ntt(a,len,1); ntt(b,len,1);56         for(int i=0;i<=len;i++) a[i]=1LL*a[i]*b[i]%mod;57         ntt(a,len,-1);58     }59 }60 61 int main(){62     NTT::getwn();63     n=read(); 64     fac[0]=1; for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;65     nfac[n]=fpow(fac[n],mod-2); for(int i=n-1;i+1;i--) nfac[i]=1LL*nfac[i+1]*(i+1)%mod;66     two[0]=1; for(int i=1;i<=n;i++) two[i]=1LL*two[i-1]*2%mod;67     for(int i=0;i<=n;i++) f[i]=1LL*two[i]*fac[i]%mod;68     for(int i=0;i<=n;i++) a[i]=1LL*(fpow(i,n+1)-1)*fpow(i-1,mod-2)%mod*nfac[i]%mod,a[i]=(a[i]+mod)%mod;69     a[0]=1; a[1]=n+1; //就是这里70     for(int i=0;i<=n;i++) b[i]=(1LL*(i&1?-1:1)*nfac[i]%mod+mod)%mod;71     NTT::work(a,b,n,n);72     for(int i=0;i<=n;i++) ans=((LL)ans+1LL*f[i]*a[i]%mod)%mod;73     printf("%d\n",ans+1);  //要把s（0,0）加上74     return 0;75 }