题意：
给定n，求$f(n)=sum limits_{i=0}^{n}{sum limits_{j=0}^{i}{S(i,j) 2^{j}{j!}}}$。
其中$S(i,j)$为第二类斯特林数。
$nleq 10^5$。
题解：
挺水的一个题。
首先这种两个变量互相约束的东西不好化简，注意到$S(i,j)$在$j>i$时是等于0而不是没有定义，所以原式
$=sum limits_{i=0}^{n}{sum limits_{j=0}^{n}{S(i,j) 2^{j}{j!}}}$
考虑斯特林数的容斥意义，有$S(i,j)=frac{1}{j!} sum limits_{k=0}^{j}{(-1)^{j-k}{jchoose k}{k^{i}}}$。
那么原式
$=sum limits_{i=0}^{n}{sum limits_{j=0}^{n}{ sum limits_{k=0}^{j}{(-1)^{j-k}{jchoose k}{k^{i}}} 2^{j}}}$
$=sum limits_{j=0}^{n}{2^{j}sum limits_{k=0}^{i}{ {(-1)^{j-k}{jchoose k}sum limits_{i=0}^{n}{k^{i}}}}}$
$=sum limits_{j=0}^{n}{2^{j}sum limits_{k=0}^{i}{ {(-1)^{j-k}{jchoose k}frac{k^{n+1}-1}{k-1}}}}$
$=sum limits_{j=0}^{n}{2^{j}sum limits_{k=0}^{i}{ {(-1)^{j-k}{frac{j!}{k!(j-k)!}}frac{k^{n+1}-1}{k-1}}}}$
$=sum limits_{j=0}^{n}{2^{j}j!sum limits_{k=0}^{i}{ {frac{(-1)^{j-k}}{(j-k)!}frac{k^{n+1}-1}{k!(k-1)}}}}$
容易发现这就是一个标准的卷积形式：
构造多项式A,B，其中$a_{i}=frac{(-1)^{i}}{i!},b_{i}=frac{i^{n+1}-1}{i!(i-1)}$，再令$C=A*B$。
（注意边界：$b_{0}=frac{0^{0}}{0!}=1,b_{1}=n+1$）
那么答案就是$f(n)=sum limits_{j=0}^{n}{2^{j}j!c_{j}}$。
复杂度$O(nlog{n})$。（其实这题还有$EI$的$O(n)$做法，orz）
套路：
- 推式子时：两个变量互相约束$ ightarrow$尽量转化成互相独立。
#include<bits/stdc++.h> #define maxn 600005 #define maxm 500005 #define inf 0x7fffffff #define mod 998244353 #define g 3 #define ll long long #define rint register ll #define debug(x) cerr<<#x<<": "<<x<<endl #define fgx cerr<<"--------------"<<endl #define dgx cerr<<"=============="<<endl using namespace std; ll fac[maxn],ifac[maxn],ind[maxn]; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline ll pw(ll a,ll b){ll r=1;while(b)r=(b&1)?r*a%mod:r,a=a*a%mod,b>>=1;return r;} struct poly{ ll a[maxn],n; inline void clear(){memset(a,0,sizeof(a)),n=0;} inline void ntt(ll op){ for(ll i=0;i<n;i++) if(i>ind[i]) swap(a[i],a[ind[i]]); for(ll l=1;l<=n;l<<=1){ ll p=pw(g,(mod-1)/l); if(op==-1) p=pw(p,mod-2); for(ll i=0;i<n;i+=l) for(ll j=i,w=1;j<i+l/2;j++,w=w*p%mod){ ll x=a[j],y=w*a[j+l/2]%mod; a[j]=(x+y)%mod,a[j+l/2]=(x-y+mod)%mod; } } if(op==-1){ ll w=pw(n,mod-2); for(ll i=0;i<n;i++) a[i]=a[i]*w%mod; } } poly operator*(const poly b)const{ poly res; res.clear(),res.n=n; for(ll i=0;i<n;i++) res.a[i]=a[i]*b.a[i]%mod; return res; } }; int main(){ ll n=read(),m=1,ans=0; while(m<=2*n) m<<=1; fac[0]=1; for(ll i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; ifac[n]=pw(fac[n],mod-2); for(ll i=n-1;i>=0;i--) ifac[i]=ifac[i+1]*(i+1)%mod; poly A,B; A.clear(),B.clear(),A.n=B.n=m; for(ll i=0;i<=n;i++){ if(i==0) A.a[i]=1; else if(i==1) A.a[i]=n+1; else A.a[i]=(pw(i,n+1)-1)*ifac[i]%mod*pw(i-1,mod-2)%mod; } for(ll i=0,j=1;i<=n;i++,j=j*(mod-1)%mod) B.a[i]=j*ifac[i]%mod; for(ll i=0;i<m;i++) ind[i]=(i&1)?((ind[i>>1]>>1)|(m>>1)):(ind[i>>1]>>1); A.ntt(1),B.ntt(1); poly C=A*B; C.ntt(-1); for(ll i=0;i<=n;i++) ans=(ans+pw(2,i)*fac[i]%mod*C.a[i]%mod)%mod; printf("%lld ",ans); return 0; }