题目概述

求 $f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i}S(i,j)\cdot2^j\cdot j!$ ，$S(i,j)$ 表示第二类斯特林数。

解题报告

$S(i,j)$ 表示把 $i$ 个不同的球放进 $j$ 个相同的盒子且没有盒子为空的方案数，那么根据实际意义可以得出：

$S(i,j)=j\cdot S(i-1,j)+S(i-1,j-1)$ ，也就是枚举第一个球是否单独放进一个盒子里。

上面的式子和这题基本没有什么关系……因为这题要求的是 $g(n)=\sum_{i=0}^{n}S(n,i)\cdot 2^i\cdot i!$ 的前缀和。

考虑实际意义，可以认为是把 $n$ 个不同的球放进至多 $n$ 个不同的盒子且每个盒子可以选择两种状态的方案数。

于是得出递推式：$g(n)=\sum_{i=1}^{n}2{n\choose i}g(n-i)$ （枚举第一个盒子中放多少个球）。

然后就开始骚操作了QAQ：

$$ g(n)=\sum_{i=1}^{n}{2n!\over (n-i)!\cdot i!}g(n-i) $$

考虑把长得像的搞在一起，于是除以个 $n!$ ：

$$ {g(n)\over n!}=\sum_{i=1}^{n}{2\over i!}\cdot{g(n-i)\over (n-i)!} $$

这竟然是个卷积……令 $A(n)=\sum_{i=1}^{n}{2\over i!}x^i,B(n)=\sum_{i=0}^{n}{g(n-i)\over (n-i)!}x^i$ ，那么：$B(n)=A(n)*B(n)+1$ 。

为什么要加 $1$ ？因为 $A(n)$ 是没有常数项的，导致卷不出 $B(0)$ ，所以要补上常数项 $B(0)$ 使两边的多项式相等。

那么 $B(n)={1\over 1-A(n)}$ ，多项式除法？

接下来是多项式求逆黑科技：

$$ A(n)B(n)\equiv1(mod\ x^n)\\ [A(n)B(n)-1]^2\equiv0(mod\ x^{2n})\\ A^2(n)B^2(n)-2A(n)B(n)+1\equiv0(mod\ x^{2n})\\ A(n)[2B(n)-A(n)B^2(n)]\equiv1(mod\ x^{2n}) $$

所以求出模 $x^n$ 意义下的 $B(n)$ 就可以得出模 $x^{2n}$ 意义下的 $B(n)$ ，边界条件是 $n=1$ 的时候，这时候只有常数项，所以只要求 $A(n)$ 常数项的逆元就行了。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100000,maxm=1<<18,MOD=998244353;

int n,m,rev[maxm+5],pw[2][maxm+5],INV[maxm+5],A[maxm+5],B[maxm+5],ans;

inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i++) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int y) {if ((x+=y)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=1;i<n;i++) if (rev[i]<i) swap(a[rev[i]],a[i]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) {int inv=Pow(n,MOD-2);for (int i=0;i<n;i++) a[i]=(LL)a[i]*inv%MOD;}
}
int C[maxm+5];
void Inv(int *a,int *b,int n){
    if (n==1) {b[0]=Pow(a[0],MOD-2);return;}
    Inv(a,b,n>>1);Pre(n<<1);for (int i=0;i<n;i++) B[i]=a[i],B[i+n]=0;NTT(B,n<<1,1);NTT(b,n<<1,1);
    for (int i=0;i<(n<<1);i++) B[i]=((b[i]<<1)%MOD+MOD-(LL)B[i]*b[i]%MOD*b[i]%MOD)%MOD;
    NTT(B,n<<1,-1);for (int i=0;i<n;i++) b[i]=B[i],b[i+n]=0;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    for (int i=2;i<=n;i++) INV[i]=(LL)INV[i]*INV[i-1]%MOD;
    for (int i=1;i<=n;i++) INV[i]=(MOD-(INV[i]<<1)%MOD)%MOD;INV[0]=1;
    m=0;while ((1<<m)<=n) m++;m=1<<m;Inv(INV,A,m);ans=A[0];
    for (int i=1,fac=1;i<=n;i++) AMOD(ans,(LL)A[i]*(fac=(LL)fac*i%MOD)%MOD);printf("%d\n",ans);return 0;
}