【题解】[HEOI2016/TJOI2016] 求和 第二类斯特林数 BZOJ – 4555

题目链接=￣ω￣=

$$f(n) = \sum _ {i = 0} ^ n \sum _ {j = 0} ^ i S(i, j) \times 2 ^ j \times j!$$

因为当 $i < j$时 $S(i, j) = 0$，所以式子可以写成：

$$
\begin{equation}
\begin{aligned}
f(n) &= \sum _ {i = 0} ^ n \sum _ {j = 0} ^ n S(i, j) \times 2 ^ j \times j! \\
&= \sum _ {j = 0} ^ n 2 ^ j! \times \sum _ {i = 0} ^ n S(i, j)
\end{aligned}
\end{equation}
$$

第二类斯特林数容斥计算：

$$S(n, k) = \frac 1 {k!} \times \sum _ {i = 0} ^ k (-1) ^ i \times C _ k ^ i \times (k – i) ^ n$$

代入：

$$
\begin{equation}
\begin{aligned}
f(n) &= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {i = 0} ^ n S(i, j) \\
&= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {i = 0} ^ n [\frac 1 {j!} \times \sum _ {k = 0} ^ j (-1) ^ k \times C _ j ^ k \times (j – k) ^ i] \\
&= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {i = 0} ^ n \sum _ {k = 0} ^ j [\frac {(-1) ^ k} {k!} \times \frac {(j – k) ^ i} {(j – k)!}] \\
&= \sum _ {j = 0} ^ n 2 ^ j \times j! \times \sum _ {k = 0} ^ j [\frac {(-1) ^ k} {k!} \times \frac {\sum _ {i = 0} ^ n (j – k) ^ i} {(j – k)!}]
\end{aligned}
\end{equation}
$$

设：

$$f(i) = \frac {(-1) ^ i} {i!}$$
$$g(i) = \frac {\sum _ {j = 0} ^ n i ^ j} {i!}$$

$g$可以用等比数列求和公式算

就有：

$$f(n) = \sum _ {i = 0} ^ n 2 ^ i \times i! \times (f \times g)(i)$$

其中 $(f \times g)(i)$表示 $f$与 $g$的卷积的第 $i$项

于是就能 ntt 了。。。

复杂度 $O(n \log _ 2 n)$

#include <bits/stdc++.h>

#define NS (262150)
#define MOD (998244353)
#define G (3)
#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) < 0 ? (a) - (b) + MOD : (a) - (b))
#define mul(a, b) (1ll * (a) * (b) % MOD)
#define inv(a) (qpow((a), MOD - 2))

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int qpow(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1) res = mul(res, a);
        a = mul(a, a), b >>= 1;
    }
    return res;
}

int n, fac[NS], fiv[NS];

int rev[NS];

struct poly
{
    int d[NS], N, bs;
    int& operator [] (const int a) {return d[a];}
    void resize(int l)
    {
        N = 1, bs = 0;
        while (N < l) N <<= 1, bs++;
    }
    void ntt(int t)
    {
        for (int i = 0; i < N; i += 1)
        {
            rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bs - 1));
            if (i < rev[i]) swap(d[i], d[rev[i]]);
        }
        for (int l = 1; l < N; l <<= 1)
        {
            int dt = qpow(G, (MOD - 1) / (l << 1));
            if (t == -1) dt = inv(dt);
            for (int i = 0; i < N; i += (l << 1))
            {
                int g = 1, t1, t2;
                for (int j = i; j < i + l; j += 1, g = mul(g, dt))
                {
                    t1 = d[j], t2 = mul(d[j + l], g);
                    d[j] = pls(t1, t2), d[j + l] = mns(t1, t2);
                }
            }
        }
        if (t == -1)
        {
            int iv = inv(N);
            for (int i = 0; i < N; i += 1) d[i] = mul(d[i], iv);
        }
    }
    void operator *= (poly &oth)
    {
        for (int i = 0; i < N; i += 1) d[i] = mul(d[i], oth[i]);
    }
} A, B;

int main(int argc, char const* argv[])
{
    IN(n), A.resize(n << 1 | 1), B.resize(n << 1 | 1), fac[0] = 1;
    for (int i = 1; i <= n; i += 1) fac[i] = mul(fac[i - 1], i);
    fiv[n] = inv(fac[n]);
    for (int i = n - 1; i >= 0; i -= 1) fiv[i] = mul(fiv[i + 1], (i + 1));
    for (int i = 0; i <= n; i += 1)
    {
        if (i & 1) A[i] = mul(mns(0, 1), fiv[i]);
        else A[i] = fiv[i];
        if (i == 1) B[i] = pls(n, 1);
        else B[i] = mul(mul(mns(qpow(i, n + 1), 1), inv(mns(i, 1))), fiv[i]);
    }
    A.ntt(1), B.ntt(1), A *= B, A.ntt(-1);
    int ans = 0;
    for (int i = 0, j = 1; i <= n; i += 1, j = pls(j, j))
        ans = pls(ans, mul(mul(j, fac[i]), A[i]));
    printf("%d\n", ans);
    return 0;
}