一道推起来不太麻烦的题……(所以为啥去年这题只有zcg写了正解，还是$O(nlog^2n)$的分治NTT……)
虽然不完全是自己推的(推式子的过程中看了别人的式子两眼……)，不过还是写写过程好了。
egin{equation}Ans=sum_{i=0}^nsum_{j=0}^i S(i,j)2^j(j!)end{equation}
因为$n<m$时有$S(n,m)=0$，因此$j$的枚举上界可以直接改成$n$。
egin{equation}Ans=sum_{i=0}^nsum_{j=0}^n S(i,j)2^j(j!)end{equation}
考虑第二类斯特林数的实际意义，$S(n,m)$表示把$n$个不同小球放进$m$个相同盒子且每个盒子均非空的方案数，那么$S(n,m)(m!)$就变成了每个盒子不同。
运用容斥原理，$m个盒子均非空的方案数=所有盒子无限制的方案数-1个盒子为空的方案数+2个盒子为空的方案数-3个盒子为空的方案数……$，也就是说
egin{equation}S(n,m)(m!)=sum_{i=0}^m(-1)^i(m-i)^n C_m^iend{equation}
这个式子的意思就是首先枚举强制为空的盒子数，其余盒子因为无限制所以随便放，因为小球不同所以方案数是$(m-i)^n$， 再乘上从$m$个盒子中选$i$个盒子强制为空的方案即为总方案数。
把这个式子代入，得
egin{equation}Ans=sum_{i=0}^nsum_{j=0}^n 2^j(j!)sum_{k=0}^j(-1)^k(j-k)^i C_j^k\=sum_{i=0}^nsum_{j=0}^n 2^j(j!)sum_{k=0}^j(-1)^{j-k}k^i C_j^k\=sum_{j=0}^n 2^jsum_{k=0}^j(-1)^{j-k}C_j^ksum_{i=0}^n k^i\=sum_{j=0}^n 2^jsum_{k=0}^jfrac{(-1)^{j-k}(j!)sum_{i=0}^n k^i}{k!(j-k)!}\=sum_{j=0}^n 2^j(j!)sum_{k=0}^jfrac{sum_{i=0}^n k^i}{k!}*frac{(-1)^{j-k}}{(j-k)!}end{equation}
显然右边是一个卷积形式，令
egin{equation}A_i=frac{sum_{j=0}^n i^j}{i!}\B_i=frac{(-1)^i}{i!}end{equation}
那么有
egin{equation}Ans=sum_{j=0}^n 2^j(j!)(A*B)_jend{equation}
再把等比数列求和公式代入$A$的表达式即可，记得特判$i=1$。
egin{equation}A_i=left{egin{array}{l}frac{n+1}{i!},i=1\frac{i^{n+1}-1}{(i-1)(i!)},Otherwiseend{array} ight.end{equation}
然后就可以NTT了，复杂度$O(nlog n)$。(话说分治NTT的做法怎么搞来着……)
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=262200,p=998244353,g=3; 6 void NTT(int*,int,int); 7 int qpow(int,int,int); 8 int n,N=1,f[maxn],A[maxn],B[maxn],ans=0; 9 int main(){ 10 freopen("heoi2016_sum.in","r",stdin); 11 freopen("heoi2016_sum.out","w",stdout); 12 scanf("%d",&n); 13 while(N<=(n<<1))N<<=1; 14 f[0]=1; 15 for(int i=0;i<=n;i++){ 16 if(i)f[i]=(long long)f[i-1]*i%p; 17 B[i]=qpow(f[i],p-2,p); 18 if(i!=1)A[i]=(qpow(i,n+1,p)-1+p)%p*(long long)qpow((i-1+p)%p*(long long)f[i]%p,p-2,p)%p; 19 else A[i]=(long long)(n+1)*B[i]%p; 20 if(i&1)B[i]=(p-B[i])%p; 21 } 22 NTT(A,N,1); 23 NTT(B,N,1); 24 for(int i=0;i<N;i++)A[i]=(long long)A[i]*B[i]%p; 25 NTT(A,N,-1); 26 for(int i=0,pw=1;i<=n;i++,pw=(long long)pw*2%p)ans=(ans+(long long)pw*f[i]%p*A[i]%p)%p; 27 printf("%d",ans); 28 return 0; 29 } 30 void NTT(int *A,int n,int tp){ 31 for(int i=1,j=0,k;i<n-1;i++){ 32 k=n; 33 do j^=(k>>=1);while(j<k); 34 if(i<j)swap(A[i],A[j]); 35 } 36 for(int k=2;k<=n;k<<=1){ 37 int wn=qpow(g,(tp>0?(p-1)/k:(p-1)/k*(long long)(p-2)%(p-1)),p); 38 for(int i=0;i<n;i+=k){ 39 int w=1; 40 for(int j=0;j<(k>>1);j++,w=(long long)w*wn%p){ 41 int a=A[i+j],b=(long long)w*A[i+j+(k>>1)]%p; 42 A[i+j]=(a+b)%p; 43 A[i+j+(k>>1)]=(a-b+p)%p; 44 } 45 } 46 } 47 if(tp<0){ 48 int inv=qpow(n,p-2,p); 49 for(int i=0;i<n;i++)A[i]=(long long)A[i]*inv%p; 50 } 51 } 52 int qpow(int a,int b,int p){ 53 int ans=1; 54 for(;b;b>>=1,a=(long long)a*a%p)if(b&1)ans=(long long)ans*a%p; 55 return ans; 56 }
顺便一提……
成就达成：HEOI2016全部AC，哈哈……装B
