[NTT][HEOI2016/TJOI2016]求和

题目传送门：https://www.luogu.org/problemnew/show/P4091

----------

####题目描述
在2016年，佳媛姐姐刚刚学习了第二类斯特林数，非常开心。

现在他想计算这样一个函数的值:

$$f(n)=\sum_{i=0}^n\sum_{j=0}^i S(i,j)\times 2^j \times (j!)$$
S(i, j)表示第二类斯特林数，递推公式为:

$$S(i, j) = j \times S(i - 1, j) + S(i - 1, j - 1), 1 \le j \le i - 1$$

边界条件为： $$S(i, i) = 1(0 \le i), S(i, 0) = 0(1 \le i)$$

你能帮帮他吗?

####输入格式：
输入只有一个正整数

####输出格式：
输出f(n)。由于结果会很大，输出f(n)对998244353(7 × 17 × 223 + 1)取模的结果即可。

----------
###题解
首先，斯特林数有一种容斥原理的公式：
$$S(n,m)=\frac{1}{m!}\sum_{k=0}^m(−1)^kC(m,k)(m−k)^n$$
把它带进题目的公式中，得：
$$\sum_{i=0}^n\sum_{j=0}^i\frac{1}{j!}*j!*2^j\sum_{k=0}^j(-1)^kC(j,k)(j-k)^i$$
消掉$j!$
$$\sum_{i=0}^n\sum_{j=0}^i2^j\sum_{k=0}^j(-1)^kC(j,k)(j-k)^i$$
拆开组合数：
$$\sum_{i=0}^n\sum_{j=0}^i2^j\sum_{k=0}^j(-1)^k\frac{j!}{(j-k)!k!}(j-k)^i$$
提出$j!$，重新组合：
$$\sum_{i=0}^n\sum_{j=0}^i2^j*j!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{(j-k)^i}{(j-k)!}$$
改变枚举顺序：
$$\sum_{j=0}^n2^j*j!\sum_{k=0}^j\frac{(-1)^k}{k!}\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!}$$
令
$$f(x)=\frac{(-1)^k}{k!}$$
$$g(x)=\frac{\sum_{i=0}^n(j-k)^i}{(j-k)!}$$
那么原式就可以写成：
$$\sum_{j=0}^n2^j*j!\sum_{x+y=j} f(x)*g(y)$$
卷积形式，NTT直接上就好了。
$g(x)$的形式是一个等比数列，用等比数列求和公式即可。

----------
贴上代码：
```
#include<stdio.h>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define mod 998244353
#define maxn 1000005
using namespace std;
const ll g=3;
ll omega[maxn],N=1;
ll a[maxn],b[maxn],fact[maxn],ans[maxn];
ll t0[maxn],t1[maxn],t2[maxn];
ll ksm(ll a,ll b)
{
    ll s=1;
    while(b)
    {
        if(b&1) s=(s*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return s;
}
void NTT(ll *A,ll n,ll type)
{
    ll t0,t1;
    for(ll i=0,j=0;i<n;i++)
    {
        if(i<j) swap(A[i],A[j]);
        for(ll k=(n>>1);(j^=k)<k;k>>=1);
    }
    omega[0]=1;
    for(ll m=1;m<n;m<<=1)
    {
        t0=ksm(g,(mod-1+type*(mod-1)/(m<<1))%(mod-1));
        for(ll i=1;i<m;i++) omega[i]=omega[i-1]*t0%mod;
        for(ll k=0;k<n;k+=(m<<1))
        {
            for(ll i=k;i<k+m;i++)
            {
                t0=A[i];
                t1=(A[i+m]*omega[i-k])%mod;
                A[i]=(t0+t1)%mod;
                A[i+m]=((t0-t1)%mod+mod)%mod;
            }
        }
    }
    if(type==1) return;
    t0=ksm(n,mod-2);
    for(ll i=0;i<n;i++) A[i]=A[i]*t0%mod;
}
void mul(ll *A,ll *B,ll *C)
{
    for(int i=0;i<N;i++) t0[i]=A[i],t1[i]=B[i];
    NTT(t0,N,1),NTT(t1,N,1);
    for(int i=0;i<N;i++) t2[i]=(t0[i]*t1[i])%mod;
    NTT(t2,N,-1);
    for(int i=0;i<N;i++) C[i]=t2[i];
}
int main()
{
    ll n;
    scanf("%lld",&n);
    while(N<=2*n) N<<=1;
    fact[0]=1;
    for(int i=1;i<=n;i++) fact[i]=fact[i-1]*i%mod;
    a[0]=1;
    for(int i=1;i<=n;i++)
    {
        a[i]=i&1?mod-1:1;
        a[i]=(a[i]*ksm(fact[i],mod-2))%mod;
    }
    b[0]=1,b[1]=n+1;
    for(int i=2;i<=n;i++)
    {
        b[i]=ksm(i,n+1);
        b[i]=((b[i]-1)%mod+mod)%mod;
        b[i]=(b[i]*ksm(fact[i],mod-2))%mod;
        b[i]=(b[i]*ksm(i-1,mod-2))%mod;
    }
    mul(a,b,ans);
    ll tot=0,p2=1;
    for(int i=0;i<=n;i++)
    {
        tot=(tot+((p2*fact[i])%mod*ans[i])%mod)%mod;
        p2=(p2*2)%mod;
    }
    printf("%lld",tot);
}
```

PhantasmDragon 's Blog