写于:2019-01-13 20:44

更新于:2019-03-16 11:45

二项式反演:

\begin{aligned} f_n=\sum_{i=0}^{n}(-1)^i {n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^i {n \choose i} f_i \\ f_n=\sum_{i=0}^{n}{n \choose i} g_i &\Leftrightarrow g_n=\sum_{i=0}^{n}(-1)^{n-i} {n \choose i} f_i \end{aligned}

BZOJ2839 集合计数 ▷ 2019-01-13

a(i) 表示大于等于 i 的方案数,则:

a(i) = {n \choose i} (2^{2^{n-i}}-1)

f(i) 表示容斥系数,使得:

ans = \sum\limits_{i=0}^n f(i) \times a(i)

b(i) 为恰好为 i 的方案数,b(i) 为容斥系数,使得

ans = \sum_{i=0}^\infty g(i) \times b(i)

考虑单个集合并为 x 的选取方案对 ans 的贡献,易得到:

g(x) = [ x = k ]

考虑到每个恰好为 x 的答案会被所有小于等于 xa_i 所贡献

g(x) = \sum\limits_{i=0}^x {x \choose i} f(i)

二项式反演得:

\begin{aligned} f(x) &= \sum\limits_{i=0}^x {x \choose i} (-1)^{x-i} g(x) \\ &= {x \choose k} (-1)^{x-k} [x \ge k] \end{aligned}

代入得:

\begin{aligned} ans &= \sum\limits_{i=0}^n f(i) \times a(i) \\ &= \sum\limits_{i=0}^n {i \choose k} (-1)^{i-k} [i \ge k] \times {n \choose i} (2^{2^{n-i}} - 1) \\ &= \sum\limits_{i=k}^n (-1)^{i-k} (2^{2^{n-i}} - 1) {i \choose k} {n \choose i} \end{aligned}

即可 O(n \log n) 求解

代码:

// =================================
//   author: memset0
//   date: 2019.01.13 20:04:47
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 1e6 + 10, mod = 1e9 + 7;
int n, k, now, ans;
int fac[N], inv[N];

inline int C(int n, int m) {
    return (ll)fac[n] * inv[m] % mod * inv[n - m] % mod;
}

inline int fpow(int a, int b, int mod) {
    int s = 1;
    for (; b; b >>= 1, a = (ll)a * a % mod)
        if (b & 1) s = (ll)s * a % mod;
    return s;
}

void main() {
    read(n), read(k), fac[0] = fac[1] = inv[0] = inv[1] = 1;
    for (int i = 2; i <= n; i++) fac[i] = (ll)fac[i - 1] * i % mod;
    for (int i = 2; i <= n; i++) inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;
    for (int i = 2; i <= n; i++) inv[i] = (ll)inv[i - 1] * inv[i] % mod;
    for (int i = k; i <= n; i++) {
        now = (i - k) & 1 ? -1 : 1;
        now = (ll)now * C(n, i) % mod;
        now = (ll)now * C(i, k) % mod;
        now = (ll)now * (fpow(2, fpow(2, n - i, mod - 1), mod) - 1) % mod;
        ans = (ans + now) % mod;
    }
    print((ans + mod) % mod, '\n');
}

} signed main() { return ringo::main(), 0; }

LJOJ5233 ACE
上一篇 «
LJOJ5285 Endless
» 下一篇