Description：

求： $$ f(n)=\sum_{i=0}^n\sum_{j=0}^i S_2(i,j)\times 2^j \times (j!) $$ $1\leqslant n\leqslant 10^5$

Solution：

当 $j>i$ 时 $S_2(i,j)=0$ ，把 $S_2(i,j)$ 展开，就是： $$ \sum_{i=0}^n\sum_{j=0}^n\frac1{j!}\sum_{k=0}^j\frac{j!}{k!(j-k)!}(-1)^{j-k}k^i\times 2^j \times (j!) $$ 交换求和号： $$ \sum_{j=0}^n2^jj!\sum_{k=0}^j\frac{\begin{align}\sum_{i=0}^nk^i\end{align}}{k!}\frac{(-1)^{j-k}}{(j-k)!} $$ 第一个分式上面那个是一个等比数列求和，然后就是一个卷积的形式，可以 $NTT$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 400010

#define P 998244353

typedef long long ll;

ll fac[MAXN],inv[MAXN];

ll power(ll a,ll b)

{

    ll res = 1;

    while(b > 0)

    {

        if(b & 1)res = res * a % P;

        a = a * a % P;

        b = b >> 1;

    }

    return res;

}

ll a[MAXN],b[MAXN],s[MAXN];

int rev[MAXN];

ll ww[MAXN << 1],*g = ww + MAXN;

void NTT(ll f[],int l,int type)

{

    for(int i = 0;i < l;++i)

    {

        if(i < rev[i])swap(f[i],f[rev[i]]);

    }

    for(int i = 2;i <= l;i = i << 1)

    {

        ll wn = g[type * l / i];

        for(int j = 0;j < l;j += i)

        {

            ll w = 1;

            for(int k = j;k < j + i / 2;++k)

            {

                ll u = f[k],t = w * f[k + i / 2] % P;

                f[k] = (u + t) % P;

                f[k + i / 2] = (u - t + P) % P;

                w = w * wn % P;

            }

        }

    }

    if(type == -1)

    {

        ll ni = power(l,P - 2);

        for(int i = 0;i < l;++i)

        {

            f[i] = f[i] * ni % P;

        }

    }

    return;

}

int main()

{

    scanf("%d",&n);

    fac[0] = 1;

    for(ll i = 1;i <= n;++i)fac[i] = fac[i - 1] * i % P;

    inv[n] = power(fac[n],P - 2);

    for(ll i = n - 1;i >= 0;--i)inv[i] = inv[i + 1] * (i + 1) % P;

    for(ll i = 0;i <= n;++i)

    {

        if(i != 1)a[i] = (power(i,n + 1) - 1 + P) % P * power((i - 1 + P) % P,P - 2) % P;

        else a[i] = n + 1;

        a[i] = a[i] * inv[i] % P;

        b[i] = inv[i] * power(P - 1,i) % P;

    }

    int l = 0,len = 1;

    for(;len <= (n << 1);len = len << 1)++l;

    for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

    g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

    for(int i = 2;i < len;++i)g[i] = g[i - len] = g[i - 1] * g[1] % P;

    ll ans = 0;

    NTT(a,len,1);NTT(b,len,1);

    for(int i = 0;i < len;++i)s[i] = a[i] * b[i] % P;

    NTT(s,len,-1);

    for(int j = 0;j <= n;++j)

    {//cout << s[j] << " ";

        ans = (ans + s[j] * power(2,j) % P * fac[j] % P) % P;

    }

    cout << ans << endl;

    return 0;

}