luogu P4091 [HEOI2016/TJOI2016]求和 FFT

又是一道神仙题orz

我们先化一化式子。

\(\displaystyle Ans[n]=\sum_{i=0}^n\sum_{j=0}^iS(i,j)\times 2^j\times (j!)\)

看着\(\displaystyle \sum_{j=0}^i\)很不爽，因为当\(j>i\)时，\(S(i,j)=0\),所以

\(\displaystyle Ans[n]=\sum_{i=0}^n\sum_{j=0}^nS(i,j)\times 2^j\times (j!)\)

看着\(S(i,j)\)很不爽，我们先把它单独拎出来。

$\displaystyle Ans[n]=\sum_{j=0}^n2^j\times (j!)\sum_{i=0}^nS(i,j) $

注意这里枚举\(i,j\)的顺序发生了改变，但式子依然等价。

这里先放个结论:

\(\displaystyle S(i,j)=\frac{1}{j!}\sum_{k=0}^j(-1)^k C_{j}^{k} (j-k)^i\)

这个可以用容斥原理来解释，第二类斯特林数是将i个不同的球，j个相同的盒子，不能空的方案数，现将盒子看成不一样的，并且能空，枚举空盒的个数\(C_{j}^{k}\), 其余的随便放\((j-k)^i\), 乘上容斥系数\((-1)^k\),在乘上\(\displaystyle \frac{1}{j!}\)将盒子变成一样的。

带进\(\displaystyle S(i,j)=\frac{1}{j!}\sum_{k=0}^j(-1)^k C_{j}^{k} (j-k)^i\)发现:

$\displaystyle Ans[n]=\sum_{j=0}^n2^j\times (j!)\sum_{i=0}^n \frac{1}{j!}\sum_{k=0}^j(-1)^k C_{j}^{k} (j-k)^i $

$\displaystyle Ans[n]=\sum_{j=0}^n2^j \sum_{i=0}^n \sum_{k=0}^j(-1)^k C_{j}^{k} (j-k)^i $

将\(\displaystyle C_j^k=\frac{j!}{k!(j-k)!}\) 带进去。

$\displaystyle Ans[n]=\sum_{j=0}^n2^j \sum_{i=0}^n \sum_{k=0}^j(-1)^k \frac{j!}{k!(j-k)!} (j-k)^i $

$\displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! \sum_{i=0}^n \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{(j-k)^i}{(j-k)!} $

看着\(\displaystyle \frac{(j-k)^i}{(j-k)!}\)非常不清真，又因为只有它带着\(i\),所以我们再次改变枚举顺序。

$\displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! \sum_{k=0}^j \frac{(-1)^k}{k!} \frac{\sum_{i=0}^n(j-k)^i}{(j-k)!} $

我们设\(\displaystyle f[k]=\frac{(-1)^k}{k!}\) \(\displaystyle g[k]=\frac{\sum_{i=0}^n k^i}{k!}\)式子就变成了

$\displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! \sum_{k=0}^j f[k]g[j-k] $

$\displaystyle Ans[n]=\sum_{j=0}^n 2^j (j)! (f*g)(j) $

\((f*g)(j)\)的含义就是\(f\)卷上\(g\)后\(x^j\)的系数。

后面的\(\displaystyle g[k]=\frac{\sum_{i=0}^n k^i}{k!}\)貌似可以等比数列求和，根据等比数列求和的知识我们知道\(\displaystyle \sum_{i=0}^n k^i=\frac{k^{n+1}-1}{k-1}\)

所以\(\displaystyle g[k]=\frac{k^{n+1}-1}{(k-1)k!}\)

注意

\(g[0]=1\)（\(0^0\)并没有意义，但是\(S(0,0)=1\),所以\(g[0]=1\)）。

\(g[1]=n+1\),（k=1时并不能等比数列求和，但显然\(g[1]=n+1\)）

NTT一波带走就行了。

#include<iostream>
#include<cstdio>
#define DB double
#define LL long long
using namespace std;
int n;
const int N = 400010, mod = 998244353, G = 3, Ginv = (mod + 1) / 3;
int r[N];
LL ans, two = 1;
LL g[N], f[N], jc[N], inv[N];
LL ksm(LL a, LL b, LL mod) 
{
    LL res = 1;
    for (; b; b >>= 1, a = a * a % mod)
        if (b & 1)res = res * a % mod;
    return res;
}
void NTT(LL *A, int lim, int opt) 
{
    for (int i = 0; i < lim; ++i)
        if (i < r[i])swap(A[i], A[r[i]]);
    int len;
    LL wn, w, x, y;
    for (int mid = 1; mid < lim; mid <<= 1) 
    {
        len = mid << 1;
        wn = ksm(opt == 1 ? G : Ginv, (mod - 1) / len, mod);
        for (int j = 0; j < lim; j += len) 
        {
            w = 1;
            for (int k = j; k < j + mid; ++k, w = w * wn % mod) 
            {
                x = A[k]; y = A[k + mid] * w % mod;
                A[k] = (x + y) % mod;
                A[k + mid] = (x - y + mod) % mod;
            }
        }
    }
    if (opt == 1)return;
    int ni = ksm(lim, mod - 2, mod);
    for (int i = 0; i < lim; ++i)A[i] = A[i] * ni % mod;
}
void MUL(LL *A, int n, LL *B, int m) 
{
    int lim = 1;
    while (lim < (n + m))lim <<= 1;
    for (int i = 0; i < lim; ++i)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) ? (lim >> 1) : 0);
    NTT(A, lim, 1); NTT(B, lim, 1);
    for (int i = 0; i < lim; ++i)A[i] = A[i] * B[i] % mod;
    NTT(A, lim, -1);
}
void YYCH() 
{
    inv[0] = inv[1] = jc[0] = jc[1] = 1;
    for (int i = 2; i <= n; ++i)jc[i] = jc[i - 1] * i % mod;
    inv[n] = ksm(jc[n], mod - 2, mod);
    for (int i = n - 1; i >= 1; --i)inv[i] = inv[i + 1] * (i + 1) % mod;
    for (int i = 0; i <= n; ++i)f[i] = (i & 1) ? mod - inv[i] : inv[i];
    g[0] = 1; g[1] = n + 1;
    for (int i = 2; i <= n; ++i)
        g[i] = (ksm(i, n + 1, mod) - 1) * ksm(i - 1, mod - 2, mod) % mod * inv[i] % mod;
}
int main() 
{
    cin >> n;
    YYCH();
    MUL(f, n, g, n);
    for (int i = 0; i <= n; ++i, two = two * 2 % mod)
        (ans += two * jc[i] % mod * f[i] % mod) %= mod;
    cout << ans;
    return 0;
}