Luogu 4091 [HEOI2016/TJOI2016]求和

BZOJ 4555

一道模板题。

第二类斯特林数有公式：

$$S(n, m) = \frac{1}{m!}\sum_{i = 0}^{m}(-1)^i\binom{m}{i}(m - i)^n$$

考虑它的组合意义：$S(n, m)$表示$n$个不相同的小球放到$m$个相同的盒子里而且不能有空盒的方案数。

我们枚举空盒有$i$个，然后进行容斥。因为盒子没有区别，所以最后得到的值还要除以$m!$。

本题要求：

$$\sum_{i = 0}^{n}\sum_{j = 0}^{i}S(i, j)*2^j*(j!)$$

$$=\sum_{j = 0}^{n}2^j*(j!)\sum_{i = 0}^{n}S(i, j)$$

$$=\sum_{j = 0}^{n}2^j*(j!)\sum_{i = 0}^{n}\frac{1}{j!}\sum_{k = 0}^{j}(-1)^k\binom{j}{k}(j - k) ^ i$$

$$=\sum_{j = 0}^{n}2^j\sum_{i = 0}^{n}\sum_{k = 0}^{j}(-1)^k\frac{j!}{k!(j - k)!}*(j - k)^i$$

$$=\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)!}$$

记$f(i) = \frac{(-1^k)}{k!}$，$g(i) = \frac{\sum_{j = 0}^{n}i^j}{(i)!}$，

因为$S(0, 0) = (-1)^0 * 1 * 0^0 = 1$，所以记$g(0) = 1$，$g(1) = n + 1$，剩下代入等比数列求和公式。

那么原式化为

$$\sum_{i = 0}^{n}2^i*(i!)(f*g)(i)$$

做一遍$NTT$就好了。

时间复杂度$O(nlogn)$。

Code：

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const int N = 3e5 + ;

const ll P = 998244353LL;

int n, lim = , pos[N];

ll f[N], g[N], fac[N], inv[N], bin[N];

template <typename T>

inline void swap(T &x, T &y) {

    T t = x; x = y; y = t;

}

template <typename T>

inline void inc(T &x, T y) {

    x += y;

    if(x >= P) x -= P;

}

inline ll fpow(ll x, ll y) {

    ll res = 1LL;

    for (; y > ; y >>= ) {

        if (y & ) res = res * x % P;

        x = x * x % P;

    }

    return res;

}

inline void prework() {

    int l = ;

    for (; lim <= n * ; ++l, lim <<= );

    for (int i = ; i < lim; i++)

        pos[i] = (pos[i >> ] >> ) | ((i & ) << (l - ));

}

inline void ntt(ll *c, int opt) {

    for (int i = ; i < lim; i++)

        if (i < pos[i]) swap(c[i], c[pos[i]]);

    for (int i = ; i < lim; i <<= ) {

        ll wn = fpow(, (P - ) / (i << ));

        if(opt == -) wn = fpow(wn, P - );

        for (int len = i << , j = ; j < lim; j += len) {

            ll w = 1LL;

            for (int k = ; k < i; k++, w = w * wn % P) {

                ll x = c[j + k], y = w * c[j + k + i] % P;

                c[j + k] = (x + y) % P, c[j + k + i] = (x - y + P) % P;

            }

        }

    }

    if (opt == -) {

        ll invP = fpow(lim, P - );

        for (int i = ; i < lim; i++)

            c[i] = c[i] * invP % P;

    }

}

int main() {

    scanf("%d", &n);

    bin[] = fac[] = 1LL;

    for (int i = ; i <= n; i++) {

        fac[i] = fac[i - ] * i % P;

        bin[i] = bin[i - ] * 2LL % P;

    }

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

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

/*    for (int i = 0; i <= n; i++)

        printf("%lld%c", inv[i] * fac[i] % P, i == n ? '\n' : ' ');   */

    for (int i = ; i <= n; i++) {

        f[i] = ((i & ) ? (-1LL) : (1LL)) * inv[i] % P;

        if(f[i] < ) f[i] += P;

        if(i == ) g[i] = 1LL;

        else if (i == ) g[i] = n + ;

        else g[i] = (fpow(i, n + ) -  + P) % P * fpow(i - , P - ) % P;

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

    }

    prework();

    ntt(f, ), ntt(g, );

    for (int i = ; i < lim; i++) f[i] = f[i] * g[i] % P;

    ntt(f, -);

    ll ans = 0LL;

    for (int i = ; i <= n; i++)

        inc(ans, bin[i] * fac[i] % P * f[i] % P);

    printf("%lld\n", ans);

    return ;

}

巴特西

Luogu 4091 [HEOI2016/TJOI2016]求和

最新文章

热门文章