「CF1336E2」Chiori and Doll Picking (hard version)
「CF1336E2」Chiori and Doll Picking (hard version)

2020 年 04 月 26 日

给定 nn 个整数 ⟨a1,a2...an⟩\langle a_1, a_2 ... a_n \rangle，在 [0;2m)[0; 2^m) 的范围内。对于 k∈[0;m]k \in [0; m]，求选出一个子集使得异或和的二进制表示有 kk 个 11 的方案数。

1≤n≤2×105, 0≤m≤531 \leq n \leq 2 \times 10^5,\ 0 \leq m \leq 53。

题解

0x01

定义：

  • popcount⁡(x)\operatorname{popcount}(x) 表示 xx 的二进制表示下 11 的个数
  • ⟨i,j⟩=popcount(i & j)⁡\langle i, j \rangle = \operatorname{popcount(i\ \&\ j)}

对于线性基 SS，定义：

  • span⁡(S)\operatorname{span}(S) 表示 SS 张成的向量空间
  • F(S)=∑x∈span⁡(S)zxF(S) = \sum_{x \in \operatorname{span}(S)} z^x
  • P(S)=∑x∈span⁡(S)zpopcount⁡(x)P(S) = \sum_{x \in \operatorname{span}(S)} z^{\operatorname{popcount}(x)}

对于此题，定义

  • AA 为由题中给定数得到的线性基

首先你已经会了一个 O(2rank⁡(A))O(2^{\operatorname{rank}(A)}) 的暴力，下文我们介绍一种 O(2m−rank⁡(A))O(2^{m-\operatorname{rank}(A)}) 的算法，就可以通过分治在 O(2m/2)O(2^{m/2}) 的时间复杂度内通过本题。

0x02

由线性基的基本性质，可以得到：

(zx)∗F(A)=F(A)(z^x) * F(A) = F(A)

在此基础上枚举 x∈span⁡(A)x \in \operatorname{span}(A) 有

F(A)∗F(A)=F(A)⋅2rank⁡(A)FWT⁡(F(A))⋅FWT⁡(F(A))=FWT⁡(F(A))⋅2rank⁡(A)\begin{aligned} F(A) * F(A) &= F(A) \cdot 2^{\operatorname{rank}(A)} \\ \operatorname{FWT}(F(A)) \cdot \operatorname{FWT}(F(A)) &= \operatorname{FWT}(F(A)) \cdot 2^{\operatorname{rank}(A)} \end{aligned}

由于是按位相乘，考虑方程 x2=x+1x^2=x+1 的实根仅有

{x1=0x2=2rank⁡(A)\left\{ \begin{aligned} x_1 &= 0 \\ x_2 &= 2^{\operatorname{rank}(A)} \end{aligned} \right.

故 [zi]FWT⁡(F(A))∈{0,2rank⁡(A)}[z^i] \operatorname{FWT}(F(A)) \in \{0, 2^{\operatorname{rank}(A)}\}。

0x03

让我们再回到 FWT⁡\operatorname{FWT} 运算本身的意义：

[zi]FWT⁡(F(A))=∑x∈span⁡(A)(−1)⟨i,x⟩∈{0,2rank⁡(A)}\begin{aligned} [z^i] \operatorname{FWT}(F(A)) &= \sum_{x \in \operatorname{span}(A)} (-1)^{\langle i,x \rangle} \\ &\in \{ 0, 2^{\operatorname{rank}(A)} \} \\ \end{aligned}

如果存在 xx 使得 (−1)⟨i,x⟩=−1(-1)^{\langle i,x \rangle} = -1，则 FWT⁡(A)i\operatorname{FWT}(A)_i 只能为 00。

⟨x,y⟩\langle x,y \rangle 和 ⊕\oplus 运算满足结合律：

⟨i,x⟩⊕⟨j,x⟩=⟨i⊕j,x⟩\langle i,x \rangle \oplus \langle j,x \rangle = \langle i \oplus j, x \rangle

可以通过把 &\& 理解为二进制按位乘法，⊕\oplus 理解为二进制不进位加法来证明。

故我们只需检验 AA 中的每个基底而非 span⁡(A)\operatorname{span}(A) 即可判断这一位的值。

0x04

定义 AA 的正交线性基为 BB，使得对于所有 x∈span⁡(A),y∈span⁡(B)x \in \operatorname{span}(A), y \in \operatorname{span}(B)，满足 popcount(x&y)⁡\operatorname{popcount(x \& y)} 是偶数，且 rank⁡(A)+rank⁡(B)=m\operatorname{rank}(A) + \operatorname{rank}(B) = m。

根据前面的引理，有

B⋅2rank⁡(A)=FWT⁡(A)⇔IFWT⁡(B⋅2rank⁡(A))=AB \cdot 2^{\operatorname{rank}(A)} = \operatorname{FWT} (A) \Leftrightarrow \operatorname{IFWT}(B \cdot 2^{\operatorname{rank}(A)}) = A

一种简单的正交线性基构造方式是

用高斯消元整理关键位，旋转右上角到左下角得到。

证明可以考虑图中圈出矩形的左上角和右上角一定为 11，而两向量的异或的 popcount⁡\operatorname{popcount} 为偶数，那么左下角和右上角的数要么全为 00，要么全为 11。

0x05

知道了正交线性基怎么求，如何计算答案呢？

考虑用 FWT⁡\operatorname{FWT} 表示答案统计：

[zc]P(A)=[z0](A∗Gc)=[z0]IFWT⁡(FWT⁡(F(A))⋅FWT⁡(Gc))[z^c]P(A) = [z^0] (A * G^c) = [z^0] \operatorname{IFWT}(\operatorname{FWT}(F(A)) \cdot \operatorname{FWT}(G^c))

其中 GcG^c 表示 ∑x≥0zx[popcount⁡(x)=c]\sum_{x \geq 0} z^x [\operatorname{popcount}(x)=c]。

其中：

[z0]IFWT⁡(X)=2−m[z0]FWT⁡(X)=2−m∑i≥0[zi]X[z^0] \operatorname{IFWT}(X) = 2^{-m} [z^0] \operatorname{FWT}(X) = 2^{-m} \sum_{i \geq 0} [z^i] X

由于 FWT⁡(F(A))=F(B)⋅2k\operatorname{FWT}(F(A)) = F(B) \cdot 2^k，而 BB 中的元素只有 2rank⁡(B)=2m−rank⁡(A)2^{\operatorname{rank}(B)} = 2^{m - \operatorname{rank}(A)} 个。故通过暴力得到 P(B)P(B)，即可通过组合数计算得 P(A)P(A)。

[zc]P(A)=2k−m∑d≥0[zd]P(B)∑i≥0(−1)i(di)(m−dc−i)[z^c]P(A) = 2^{k-m} \sum_{d \geq 0} [z^d] P(B) \sum_{i \geq 0} (-1)^i \binom d i \binom {m-d} {c-i}

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 60, mod = 998244353;
int n, m, k, t, c[N];
long long f[N], g[N];
struct z {
  int x;
  z(int x = 0) : x(x) {}
  friend inline z operator*(z a, z b) { return (long long)a.x * b.x % mod; }
  friend inline z operator-(z a, z b) { return (a.x -= b.x) < 0 ? a.x + mod : a.x; }
  friend inline z operator+(z a, z b) { return (a.x += b.x) >= mod ? a.x - mod : a.x; }
} p[N], q[N], fac[N], ifac[N];
inline z C(int n, int m) { return n < m ? 0 : fac[n] * ifac[m] * ifac[n - m]; }
inline z fpow(z a, int b) {
  z s = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1) s = s * a;
  return s;
}
inline void insert(long long x) {
  for (int i = m - 1; i >= 0; i--)
    if ((x >> i) & 1) {
      if (f[i]) x ^= f[i];
      else {
        f[i] = x;
        return;
      }
    }
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    long long x;
    cin >> x, insert(x);
  }
  for (int i = 0; i < m; i++)
    for (int j = i + 1; j < m; j++)
      if ((f[j] >> i) & 1) f[j] ^= f[i];
  for (int i = 0; i < m; i++)
    if (f[i]) c[i] = k++;
  for (int i = 0; i < m; i++)
    if (!f[i]) c[i] = k + (t++);
  for (int i = 0; i < m; i++)
    if (f[i])
      for (int j = 0; j < m; j++)
        if ((f[i] >> j) & 1) g[c[i]] |= 1ll << c[j];
  for (int i = 0; i < k; i++)
    for (int j = k; j < m; j++)
      if ((g[i] >> j) & 1) g[j] |= 1ll << i;
  for (int i = k; i < m; i++) g[i] |= 1ll << i;
  if (k <= ((m + 1) >> 1)) {
    function<void(int, long long)> dfs = [&](int i, long long s) {
      if (i >= k) {
        p[__builtin_popcountll(s)].x++;
        return;
      }
      dfs(i + 1, s), dfs(i + 1, s ^ g[i]);
    };
    dfs(0, 0ll);
  } else {
    function<void(int, long long)> dfs = [&](int i, long long s) {
      if (i >= m) {
        q[__builtin_popcountll(s)].x++;
        return;
      }
      dfs(i + 1, s), dfs(i + 1, s ^ g[i]);
    };
    dfs(k, 0ll);
    fac[0] = ifac[0] = ifac[1] = 1;
    for (int i = 1; i <= m; i++) fac[i] = fac[i - 1] * i;
    for (int i = 2; i <= m; i++) ifac[i] = (mod - mod / i) * ifac[mod % i];
    for (int i = 1; i <= m; i++) ifac[i] = ifac[i - 1] * ifac[i];
    for (int c = 0; c <= m; c++)
      for (int d = 0; d <= m; d++)
        for (int i = 0; i <= c; i++) {
          p[c] = p[c] + fpow(2, mod - 1 + k - m) * q[d] * (i & 1 ? mod - 1 : 1) * C(d, i) * C(m - d, c - i);
        }
  }
  for (int i = 0; i <= m; i++) cout << (p[i] * fpow(2, n - k)).x << " \n"[i == m];
}

评论

TABLE OF CONTENTS

题解
0x01
0x02
0x03
0x04
0x05
代码