在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。

输入只有一个正整数

 输出f(n)。由于结果会很大，输出f(n)对998244353(7 × 17 × 223 + 1)取模的结果即可。1 ≤ n ≤ 100000

  1 /*by SilverN*/  2 #include<iostream>  3 #include<algorithm>  4 #include<cstring>  5 #include<cstdio>  6 #include<cmath>  7 #include<vector>  8 #define LL long long  9 using namespace std; 10 const int mod=998244353; 11 const int mxn=400010; 12 int read(){ 13     int x=0,f=1;char ch=getchar(); 14     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 15     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 16     return x*f; 17 } 18 LL inv[mxn],fac[mxn],invF[mxn]; 19 void init(int n){ 20     inv[1]=1;fac[0]=fac[1]=1; 21     invF[1]=invF[0]=1; 22     for(int i=2;i<=n;i++){ 23         inv[i]=((-mod/i)*inv[mod%i]%mod+mod)%mod; 24         fac[i]=fac[i-1]*i%mod; 25         invF[i]=invF[i-1]*inv[i]%mod; 26     } 27     return; 28 } 29 LL ksm(LL a,LL k){ 30     LL res=1; 31     while(k){ 32         if(k&1)res=(res*a)%mod; 33         a=(a*a)%mod; 34         k>>=1; 35     } 36     return res; 37 } 38 LL f[mxn]; 39 int N,len; 40 LL a[mxn],b[mxn]; 41 int rev[mxn]; 42  43 void NTT(LL *a,int flag){ 44     for(int i=0;i<N;i++) 45         if(i<rev[i])swap(a[i],a[rev[i]]); 46     for(int i=1;i<N;i<<=1){ 47         int p=i<<1; 48         LL gn=ksm(3,(flag==1)?(mod-1)/p:mod-1-(mod-1)/p); 49         for(int j=0;j<N;j+=p){ 50             LL g=1; 51             for(int k=0;k<i;k++,g=(LL)g*gn%mod){ 52                 LL x=a[j+k],y=(LL)g*a[j+k+i]%mod; 53                 a[j+k]=(x+y)%mod; 54                 a[j+k+i]=(x-y+mod)%mod; 55             } 56         } 57     } 58     if(flag==-1){ 59         LL Inv=ksm(N,mod-2); 60         for(int i=0;i<N;i++)a[i]=a[i]*Inv%mod; 61     } 62     return; 63 } 64 void solve(int l,int r){ 65     if(l==r)return; 66     int mid=(l+r)>>1; 67     solve(l,mid); 68     int m=r-l+1; 69     len=0; 70     for(N=1;N<m;N<<=1)len++; 71     for(int i=0;i<N;i++) 72         rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1)); 73     for(int i=0;i<N;i++)a[i]=b[i]=0; 74     for(int i=l;i<=mid;i++){ 75         a[i-l]=f[i]; 76 //        printf("i:%d f:%lld\n",i,f[i]); 77     } 78     for(int i=0;i<=r-l;i++) 79         b[i]=invF[i]; 80     NTT(a,1);NTT(b,1); 81     for(int i=0;i<N;i++)a[i]=a[i]*b[i]%mod; 82     NTT(a,-1); 83     for(int i=mid+1;i<=r;i++) 84         f[i]=(f[i]+2*a[i-l])%mod;//累加贡献 85 //    printf("mid:%d f:%lld\n",mid,f[mid+1]);  86     solve(mid+1,r); 87     return; 88 } 89 int n; 90 int main(){ 91     int i,j; 92     n=read(); 93     init(n+1); 94     f[0]=1; 95     solve(0,n); 96     LL ans=0; 97     for(int i=0;i<=n;i++){ 98 //        printf("i:%d f:%lld\n",i,f[i]); 99         ans=(ans+f[i]*fac[i]%mod)%mod;100     }101     printf("%lld\n",ans);102     return 0;103 }