BZOJ 4555: [Tjoi2016Heoi2016]求和 (NTT + 第二类斯特林数)

题意

给你一个数 \(n\) 求这样一个函数的值 :

\[\displaystyle f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i} {i \brace j} 2^j j!\]

\((1 \le n \le 100000)\)

题解

这个题直接划式子 然后 \(NTT\) 就行了qwq

需要知道一个容斥求斯特林数的东西

\[\displaystyle \begin{Bmatrix} n \\ m \end{Bmatrix} = \frac{1}{m!} \sum_{k=0}^m (-1)^k (m-k)^n\]

这个用组合意义去理解 我们考虑把 \(n\) 个物品放进 \(m\) 个盒子里中的方案数就是斯特林数(盒子不区分)

然后我们考虑枚举至少有 \(k\) 个空的盒子的方案数 那么 \(n\) 就可以随便放入剩下的 \((m-k)\) 个盒子中去

这个式子我们划一下 就可以得到一个用来 \(NTT\) 的式子...

拆一下组合数....

\[\displaystyle \begin{Bmatrix} n \\ m \end{Bmatrix} = \frac{1}{m!} \sum _{k=0}^{m} (-1)^k \frac{m!}{k!(m-k)!}(m-k)^n\]

然后再简单整理一下qwq

\[\displaystyle \begin{Bmatrix} n \\ m \end{Bmatrix} = \sum_{k=0}^{m} [\frac{(-1)^k}{k!}][\frac{(m-k)^n}{(m-k)!}]\]

然后这个就是 \(NTT\) 的式子了

对于这道题我们也可以这样做qwq

\[\displaystyle f(n)=\sum_{i=0}^{n}\sum_{j=0}^{i} \begin{Bmatrix} i \\ j \end{Bmatrix} \times 2^j \times (j!)\]

如果 \(j > i\) 时 \(\begin{Bmatrix} i \\ j \end{Bmatrix}\) 是为 \(0\) 的 (没有方案数) 那么就有

\[\displaystyle =\sum_{i=0}^{n}\sum_{j=0}^{n} \begin{Bmatrix} i \\ j \end{Bmatrix} \times 2^j \times (j!)\]

把之前的那个套进来 卷积形式 我们可以将 \(j-k\) 与 \(k\) 互换

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

不难发现只有一个地方与 \(i\) 有关 那么我们再放进去

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

然后那个是等比数列 我们用等比数列求和公式 就可以直接处理出来了

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

右边卷积就可以求出对于每个 \(j\) 的取值咯qwq

注意程序中卷积之前 要特判右边等比数列次数 \(=0,1\) 的答案 一个是 \(1\) 另一个是 \(n+1\)

代码

#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
    int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
    return x * fh;
}

void File() {
#ifdef zjp_shadow
    freopen ("4555.in", "r", stdin);
    freopen ("4555.out", "w", stdout);
#endif
}

typedef long long ll;
const ll Mod = 998244353;

ll fpm(ll x, int power) {
    ll res = 1;
    for (; power; power >>= 1, (x *= x) %= Mod)
        if (power & 1) (res *= x) %= Mod;
    return res;
}

const int N = 1 << 19;
struct Number_Theoretic_Transform {
    ll pow3[N], invpow3[N], a[N], b[N];
    int n, m, rev[N];

    void Init(int n1, int n2, ll A[], ll B[]) {
        For (i, 0, n1) a[i] = A[i];
        For (i, 0, n2) b[i] = B[i];
        m = n1 + n2;
    }

    void NTT(ll P[], int opt) {
        For (i, 0, n - 1) if (i < rev[i]) swap(P[i], P[rev[i]]);
        for (int i = 2, p; i <= n; i <<= 1) {
            p = (i >> 1);
            ll Wi = (opt == 1) ? pow3[i] : invpow3[i];
            for (int j = 0; j < n; j += i) {
                ll x = 1;
                for (int k = 0; k < p; ++ k, (x *= Wi) %= Mod) {
                    ll u = P[j + k], v = x * P[j + k + p] % Mod;
                    P[j + k] = (u + v) % Mod;
                    P[j + k + p] = (u - v + Mod) % Mod;
                }
            }
        }
        if (opt == -1) {
            ll invn = fpm(n, Mod - 2);
            For (i, 0, n - 1) (P[i] *= invn) %= Mod;
        }
    }

    void Mult() {
        int cnt = 0; for (n = 1; n <= m; n <<= 1) ++ cnt;
        for (int i = 1; i <= n; i <<= 1)
            pow3[i] = fpm(3, (Mod - 1) / i), invpow3[i] = fpm(pow3[i], Mod - 2);
        For (i, 1, n) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
        NTT(a, 1); NTT(b, 1);
        For (i, 0, n - 1) (a[i] *= b[i]) %= Mod;
        NTT(a, -1);
    }
} T;

int n;
ll a[N], b[N], fac[N], ifac[N];

void Init(int maxn) {
    fac[0] = ifac[0] = 1;
    For (i, 1, maxn) fac[i] = fac[i - 1] * i % Mod;
    ifac[maxn] = fpm(fac[maxn], Mod - 2);
    Fordown (i, maxn - 1, 1) ifac[i] = ifac[i + 1] * (i + 1) % Mod;
}

ll ans = 0;
int main () {
    File(); n = read(); Init(n);
    For (i, 0, n) {
        a[i] = (Mod + ((i & 1) ? -1 : 1) * ifac[i]) % Mod;
        if (i > 1) b[i] = (fpm(i, n + 1) - 1) * ifac[i] % Mod * fpm(i - 1, Mod - 2) % Mod;
        else if (i == 1) b[i] = n + 1;
        else if (i == 0) b[i] = 1;
    //  printf ("a[%d] = %lld; b[%d] = %lld;\n", i, a[i], i, b[i]);
    }
    T.Init(n, n, a, b);
    T.Mult();
    For (i, 0, n)
        (ans += T.a[i] * fpm(2, i) % Mod * fac[i]) %= Mod;
    printf ("%lld\n", ans);
    return 0;
}