当我跨过沉沦的一切
向着永恒开战的时候
你是我的军旗

Solution1 - 二元生成函数

注意到比较难办的一个限制即每个数只能选一次,考虑 \forall \; i \in [1, n] 用一个二元生成函数 1 + y x^{a_i} 来表示。最后我们要求的即

\forall \; i , \; [y^k \cdot x^i] \prod_{\textrm{or}} 1 + y x^{a_i}

考虑对于给 F_i(x) = 1 + y x^{a_i} 做一次 or transformation 是什么

[x^k] \operatorname{FWT_{\textrm{or}}} (F_i(x)) = \begin{cases} 1 & (a_i \notin k) \\ 1 + y & (a_i \in k) \\ \end{cases}

把点值乘起来以后每一位就是 (1+y)^\theta ,显然我们只需要对于每一项求出 [x^k] (1+y)^\theta ,这其实就是 \binom \theta k

\theta 也是好求的,每一个 F_i(x) = 1 + y x^{a_i} 只会对答案贡献 1 ,且一定是在 a_i \in k 的位置。可以直接定义 G(x) = \sum_{i=0}^\infty x^i \sum_{j=1}^n [a_j = i] ,然后做一次高维前缀和。

求出 [y^k] \prod_{\textrm{or}} F_i(x) 后,事情就变得简单了起来,一遍 interverse or transformation 加上一遍 and transformation 直接带走。

Solution2 - 容斥

cnt_S = \sum_{i=1}^n [a_i \cup S = \emptyset] ,即与 S 没有交集的 a_i 个数。

考虑对于每一个询问 \operatorname{query}(S) 统计方案数。这相当于我们硬点了一个子集里的特性没有出现过,然后容斥。

显然

\operatorname{query}(S) = \sum_{T \in S} (-1)^{|T|} \binom {cnt_T} k

求出 cnt_S 后拿 (-1)^{|T|} \binom {cnt_T} {k} 来做一趟 or transformation 即可。

Code of Solution1

// =================================
//   author: memset0
//   date: 2019.07.12 00:00:45
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define rep(i, l, r) for (int (i) = (l), __lim = (r); (i) <= __lim; (i)++)
#define for_each(i, a) for (size_t i = 0, __lim = a.size(); i < __lim; ++i)
namespace ringo {

template <class T> inline void read(T &x) {
  x = 0; char c = getchar(); 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); }
template <class T> inline void print(T a, int l, int r, std::string s = "") {
  if (s != "") std::cout << s << ": ";
  for (int i = l; i <= r; i++) print(a[i], " \n"[i == r]);
}

const int N = 5e5 + 10, M = 1 << 20, lim = M, mod = 1e9 + 7;
int n, k, m, a[N], q[N], fac[N], ifac[N], f[M];

void reader(int n, int *a) {
  static char str[21];
  for (int i = 1; i <= n; i++) {
    scanf("%s", str);
    for (int k = 0; k < 20; k++)
      a[i] |= (str[k] == '1') << k;
  }
}

inline int binom(int n, int m) {
  if (n < m) return 0;
  return 1ll * fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}

void init_fac(int lim) {
  fac[0] = fac[1] = ifac[0] = ifac[1] = 1;
  for (int i = 2; i <= lim; i++) fac[i] = 1ll * i * fac[i - 1] % mod;
  for (int i = 2; i <= lim; i++) ifac[i] = 1ll * (mod - mod / i) * ifac[mod % i] % mod;
  for (int i = 2; i <= lim; i++) ifac[i] = 1ll * ifac[i - 1] * ifac[i] % mod;
}

inline void fwt_or_without_mod(int &a, int &b) { b += a; }

inline void ufwt_or(int &a, int &b) {
  b -= a;
  if (b < 0) b += mod;
}

inline void fwt_and(int &a, int &b) {
  a += b;
  if (a >= mod) a -= mod;
}

void fwt(int *a, void trans(int&, int&)) {
  for (int len = 1; len < lim; len <<= 1)
    for (int i = 0; i < lim; i += (len << 1))
      for (int j = 0; j < len; j++) {
        trans(a[i + j], a[i + j + len]);
      }
}

void main() {
  read(n), read(k), read(m);
  reader(n, a), reader(m, q);
  init_fac(n);
  for (int i = 1; i <= n; i++) ++f[a[i]];
  fwt(f, fwt_or_without_mod);
  for (int i = 0; i < lim; i++) f[i] = binom(f[i], k);
  fwt(f, ufwt_or);
  fwt(f, fwt_and);
  for (int i = 1; i <= m; i++) print(f[q[i]], '\n');
}

} signed main() {
#ifdef memset0
  freopen("1.in", "r", stdin);
#endif
  return ringo::main(), 0;
}

巧妙的思路 容斥 FWT 二维生成函数 Favorite

已有 4 条评论

  1. Solution1 - 二元生成函数

    1. 报警了哪个人冒用我昵称啊 awa

  2. “Soltion”应该是打错了

  3. Solution 拼错了

BZOJ4401 块的计数
上一篇 «
NOI 模拟赛 20190711B 三格骨牌
» 下一篇