不错的推柿子题
题意：求$\sum\limits_{i=0}^n\sum\limits_{j=0}^nS(i,j)·2^j·j!$其中$ S(n,m)$是第二类斯特林数
$ Solution:$
首先考虑第二类斯特林数的意义：将$ n$个有标号元素放入$ m$个无标号集合（无空集）的方案数
我们枚举空集的数量容斥：$ S(n,m)=\frac{1}{m!}\sum\limits_{k=0}^m(-1)^kC_m^k(m-k)^n$
乘上$ \frac{1}{m!}$是因为容斥的集合带标号而斯特林数本身不带标号
这样可以将原式展开得：
$ \sum\limits_{i=0}^n \sum\limits_{j=0}^n2^j \sum\limits_{k=0}^j(-1)^kC_j^k(j-k)^i$ (消阶乘项)
把组合数展开得$ \sum\limits_{i=0}^n \sum\limits_{j=0}^n 2^j j! \sum\limits_{k=0}^j \frac{(-1)^k}{k!} \frac{(j-k)^i}{(j-k)!}$
改变枚举顺序得$ \sum\limits_{j=0}^n 2^j j! \sum\limits_{k=0}^j \frac{(-1)^k}{k!} \frac{ \sum\limits_{i=0}^n (j-k)^i}{(j-k)!}$
令$ A(x)= \frac{(-1)^x}{x!}$，$ B(x)=\frac{ \sum\limits_{i=0}^n x^i}{x!}$
则原式为$ \sum\limits_{j=0}^n 2^j j! \sum\limits_{k=0}^jA(k)B(j-k)$
容易发现这是一个卷积形式，而函数$ A,B$均可以在$ O(n)$时间复杂度内完成
这样可以直接用$ NTT$优化，时间复杂度:$ O(n \ log \ n)$
$ my \ code:$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#define p 998244353
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x = ; char zf = ; char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (isdigit(ch)) x = x * + ch - '', ch = getchar(); return x * zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt;
int inv[],jc[],njc[];
int ksm(int x,int y){
int ans=;
for(rt i=y;i;i>>=,x=1ll*x*x%p)if(i&)ans=1ll*ans*x%p;
return ans;
}
vector<int>A,B,f,R;int lim=;
int calc(int x,int L,int R){
if(x==)return R-L+;
return 1ll*(ksm(x,R+)-ksm(x,L))*ksm(x-,p-)%p;
}
void init(int n){
for(rt i=;i<=;i++)inv[i]=jc[i]=njc[i]=;
for(rt i=;i<=n;i++){
jc[i]=1ll*jc[i-]*i%p;
inv[i]=1ll*inv[p%i]*(p-p/i)%p;
njc[i]=1ll*njc[i-]*inv[i]%p;
}
while(lim<=n+n)lim<<=;
A.resize(lim);B.resize(lim);f.resize(lim);
A[]=;for(rt i=,tag=-;i<=n;i++,tag*=-)A[i]=tag*njc[i];
B[]=;for(rt i=;i<=n;i++)B[i]=1ll*njc[i]*calc(i,,n)%p;
}
namespace poly{
void getR(int n){
R.resize(n);
for(rt i=;i<n;i++)R[i]=(R[i>>]>>)|(i&)*(n>>);
}
void NTT(int n,vector<int>&A,int fla){
for(rt i=;i<n;i++)if(i>R[i])swap(A[i],A[R[i]]);
for(rt i=;i<n;i<<=){
int w=ksm(,(p-)//i);
for(rt j=;j<n;j+=i<<){
int K=;
for(rt k=;k<i;k++,K=1ll*K*w%p){
int x=A[j+k],y=1ll*K*A[i+j+k]%p;
A[j+k]=(x+y)%p,A[i+j+k]=(x-y)%p;
}
}
}
if(fla==-){
reverse(A.begin()+,A.end());int invn=ksm(n,p-);
for(rt i=;i<n;i++)A[i]=1ll*A[i]*invn%p;
}
}
}
using namespace poly;
int main(){
n=read();init(n);
int ans=;getR(lim);
NTT(lim,A,);NTT(lim,B,);
for(rt i=;i<lim;i++)f[i]=1ll*A[i]*B[i]%p;
NTT(lim,f,-);
for(rt i=;i<=n;i++)(ans+=1ll*ksm(,i)*jc[i]%p*f[i]%p)%=p;
cout<<(ans+p)%p;
return ;
}