Description
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。
现在他想计算这样一个函数的值:
$$f(n)=\sum_{i=0}^n\sum_{j=0}^i S(i,j)\times 2^j\times(j!)$$
$S(i,j)$表示第二类斯特林数，递推公式为:
$S(i,j)=j\times S(i-1,j)+S(i-1,j-1),1\leq j\leq i-1$。
边界条件为：$S(i,i)=1(0\leq i),S(i,0)=0(1\leq i)$
你能帮帮他吗？
Input
Output
输出$f(n)$。
由于结果会很大，输出$f(n)$对$998244353(7×17×223+1)$取模的结果即可。
题解：
递推式给你就是玩你的，一点关系都没有！
第二类斯特林数通项公式：
$$S(i,j)=\frac{1}{j!}\sum_{k=0}^j(-1)^k C_j^k(j-k)^i$$
代入原式得
$$\sum_{i=0}^n\sum_{j=0}^i \frac{1}{j!}\sum_{k=0}^j(-1)^k C_j^k(j-k)^i\times 2^j\times(j!)$$
组合数展开得
$$\sum_{i=0}^n\sum_{j=0}^i 2^j\sum_{k=0}^j(-1)^k\frac{j!}{k!(j-k)!}(j-k)^i$$
交换枚举顺序得
$$\sum_{j=0}^n(j!)2^j\sum_{k=0}^n{(-1)^k\over k!}{1\over (j-k)!}\sum_{i=0}^n(j-k)^i$$
看到又有$k$又有$j-k$，这不是卷积吗？
令 $a(x)=\sum_{x=0}^n{(-1)^x\over x!}$
$b(x)={1\over (x)!}\sum_{i=0}^n(x)^i$
则 $f(x)=(x!)2^x\sum_{i=0}^n a(x)b(x-i)$
不过循环边界到n不会越界吗？这对答案没有影响，因为斯特林数和组合数都为0。
那就直接NTT了，刚好给了一个NTT模数。（这莫非是提示？）
CODE：
#include<iostream>
#include<cstdio>
using namespace std; #define mod 998244353
int n,bit=,rev[],ans=;
long long fac[],inv[],ivf[];
long long a[],b[]; int qpow(int x,int y){
int ans=;
while(y){
if(y&)ans=1LL*ans*x%mod;
y>>=,x=1LL*x*x%mod;
}
return ans;
} void init(){
fac[]=ivf[]=inv[]=inv[]=;
for(int i=;i<=n;i++)fac[i]=fac[i-]*i%mod;
for(int i=;i<=n;i++)inv[i]=(mod-mod/i)*inv[mod%i]%mod;
for(int i=;i<=n;i++)ivf[i]=ivf[i-]*inv[i]%mod;
a[]=b[]=;
for(int i=,f=-;i<=n;i++,f=-f){
if (i==)a[i]=n+;
else a[i]=ivf[i]*(qpow(i,n+)-)%mod*inv[i-]%mod;
b[i]=f*ivf[i]%mod;
if(a[i]<)a[i]+=mod;
if(b[i]<)b[i]+=mod;
}
} void get_rev(){
while(bit<=n+n)bit<<=;
for(int i=;i<bit;i++)
rev[i]=(rev[i>>]>>)|(i&)*(bit>>);
} void NTT(long long a[],int dft){
for(int i=;i<bit;i++)
if(i<rev[i])swap(a[i],a[rev[i]]);
for(int i=;i<bit;i<<=){
long long W=qpow(,(mod-)/i/);
if(dft==-)W=qpow(W,mod-);
for(int j=;j<bit;j+=i<<){
long long w=;
for(int k=j;k<i+j;k++,w=w*W%mod){
long long x=a[k];
long long y=w*a[k+i]%mod;
a[k]=(x+y)%mod,a[k+i]=(x+mod-y)%mod;
}
}
}
int inv=qpow(bit,mod-);
if(dft==-)for(int i=;i<bit;i++)a[i]=a[i]*inv%mod;
} int main(){
scanf("%d",&n);
init();
get_rev();
NTT(a,),NTT(b,);
for(int i=;i<bit;i++)(a[i]*=b[i])%=mod;
NTT(a,-);
for(int i=;i<=n;i++){
ans+=qpow(,i)*fac[i]%mod*a[i]%mod;
if(ans>=mod)ans-=mod;
}
printf("%d",ans);
}