[ARC137D] Prefix XORs 题解

JiaY19 / 2024-11-21 / 原文

思路

考虑前缀和时每一位的贡献是什么。

对于一个生成函数 $F(x)$。

对其作 $k$ 次前缀和，函数会变成：

\[(\frac{1}{1-x})^kF(x) \]

那么其 $n$ 次项系数：

\[\begin{align} &=[x^n](\frac{1}{1-x})^kF(x)\nonumber\\ &=[x^n]F(x)(1-x)^{-k}\nonumber\\ &=\sum_{i=0}\binom{-k}{i}(-1)^i[x^{n-i}]F(x)\nonumber\\ &=\sum_{i=0}\binom{k+i-1}{i}[x^{n-i}]F(x)\nonumber \end{align} \]

这样就求出了系数为 $\binom{k+i-1}{i}$。

注意到以上是在二进制每一位考虑。

所以只有 $\binom{k+i-1}{i} \bmod 2=1$ 时才有贡献。

依据 Lucas 定理，当 $i$ 为 $k+i-1$ 子集时，答案为一。

所以最终答案为：

\[ans_i=\bigoplus_{j=0}[j\in(i+j-1)]a_{n-j} \]

我们将 $i$ 集体减一。

\[\begin{align} ans_i&=\bigoplus_{j=0}[j\in(i+j)]a_{n-j}\nonumber\\ &=\bigoplus_{j=0}[j\cap i=\emptyset]a_{n-j}\nonumber\\ \end{align} \]

容易发现是一个高维前缀和，直接做即可。

时间复杂度：$O(n\log n )$。

Code

#include <bits/stdc++.h>
using namespace std;

int n, m;
int a[1 << 20];
int b[1 << 20];

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> a[i];
  int k = 1 << 20;
  for (int i = 0; i < k; i++)
    if (i < n) b[i] = a[n - i];
  for (int i = 0; i < 20; i++)
    for (int j = 0; j < k; j++)
      if (j & (1 << i)) b[j] ^= b[j ^ (1 << i)];
  for (int i = 0; i < m; i++)
    cout << b[i ^ (k - 1)] << " \n"[i == m - 1];
}