题意：求$sum_{i=0}^{n}sum_{j=0}^{i}S(i,j)2^{j}j!$
一看就觉得不可做...
但是还是需要仔细分析的
最重要的是一步转化：
根据第二类斯特林数的定义：$S(n,m)$表示将$n$个不同物品分到$m$个集合中的方案数
然后考虑求和式里面那个东西，发现其含义就是将$i$个不同物品分到$j$个集合中，每个集合都有2种属性，然后对这些集合进行全排列的方案数
那么基于这个定义，设状态$g(n)=sum_{j=0}^{n}S(n,j)2^{j}j!$,那么有递推式：$g(n)=sum_{i=1}^{n}2C_{n}^{i}g(n-i)$
这个递推式的来历是枚举第一个集合中的元素得到的
按照套路，展开组合数，得到：
$g(n)=sum_{i=1}^{n}2frac{n!}{i!(n-i)!}g(n-i)$
移项可得：
$frac{g(n)}{n!}=sum_{i=1}^{n}frac{2}{i!}frac{g(n-i)}{(n-i)!}$
那么右边显然是个卷积的形式
设$F(x)=sum_{i=1}^{n}frac{2}{i!}x^{i}$
$G(x)=sum_{i=0}^{n}frac{g(i)}{(i)!}x^{i}$
注意到这时直接卷积后$G(0)=0$，但事实要求$G(0)=1$（边界要求）
因此可以求得$G(x)=F(x)G(x)+1$
移项即得到$G(x)=frac{1}{1-F(x)}$
（这种方法好像可以用来水分治FFT的说）
等等，求出了$G(x)$有什么用？
可以看到，对$G(x)$每一项乘$i!$即得到$g(x)$的生成函数，直接求和即可
贴代码：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #define ll long long using namespace std; const ll mode=998244353; ll F[100005]; ll FF[100005]; ll G[100005]; ll inv[100005]; ll mul[100005]; ll minv[100005]; int to[(1<<20)+5]; int n; void init() { inv[0]=inv[1]=mul[0]=mul[1]=minv[0]=minv[1]=1; for(int i=2;i<=100000;i++) { inv[i]=(mode-mode/i)*inv[mode%i]%mode; minv[i]=minv[i-1]*inv[i]%mode; mul[i]=mul[i-1]*i%mode; } } ll pow_mul(ll x,ll y) { ll ret=1; while(y) { if(y&1)ret=ret*x%mode; x=x*x%mode,y>>=1; } return ret; } void NTT(ll *a,int len,int k) { for(int i=0;i<len;i++)if(i<to[i])swap(a[i],a[to[i]]); for(int i=1;i<len;i<<=1) { ll w0=pow_mul(3,(mode-1)/(i<<1)); for(int j=0;j<len;j+=(i<<1)) { ll w=1; for(int o=0;o<i;o++,w=w*w0%mode) { ll w1=a[j+o],w2=a[j+o+i]*w; a[j+o]=(w1+w2)%mode,a[j+o+i]=((w1-w2)%mode+mode)%mode; } } } if(k==-1) { ll inv=pow_mul(len,mode-2); for(int i=1;i<(len>>1);i++)swap(a[i],a[len-i]); for(int i=0;i<len;i++)a[i]=a[i]*inv%mode; } } ll A[(1<<20)+5],B[(1<<20)+5],C[(1<<20)+5]; void get_inv(ll *f,ll *g,int dep) { if(dep==1) { g[0]=pow_mul(f[0],mode-2); return; } int nxt=(dep+1)>>1; get_inv(f,g,nxt); int lim=1,l=0; while(lim<=2*dep)lim<<=1,l++; for(int i=0;i<lim;i++)to[i]=((to[i>>1]>>1)|((i&1)<<(l-1))); for(int i=0;i<lim;i++)A[i]=B[i]=0; for(int i=0;i<dep;i++)A[i]=f[i]; for(int i=0;i<nxt;i++)B[i]=g[i]; NTT(A,lim,1),NTT(B,lim,1); for(int i=0;i<lim;i++)C[i]=A[i]*B[i]%mode*B[i]%mode; NTT(C,lim,-1); for(int i=0;i<dep;i++)g[i]=((2*g[i]-C[i])%mode+mode)%mode; } int main() { scanf("%d",&n); init(); n++; for(int i=1;i<n;i++)F[i]=(-2ll*minv[i]%mode+mode)%mode; F[0]=1; get_inv(F,FF,n); ll s=0; for(int i=0;i<n;i++)s=(s+FF[i]*mul[i]%mode)%mode; printf("%lld ",s); return 0; }