ARC137D Prefix XORs 题解

标签：XORs matrix int 题解 cdots Prefix choose 3a

这里的所有下标从 \(\bm 0\) 开始。

我们考察一下每次操作后的数列 \(a\) 会是什么样的。这里用 \(a_i\) 前面的系数 \(x\) 表示 \(a_i\) 贡献了 \(x\) 次，\(+\) 表示异或。

\[\begin{matrix} k=0&a_0&a_1&a_2&\cdots&a_{n-1}\\ k=1&a_0&a_0+a_1&a_0+a_1+a_2&\cdots&{n-1\choose 0}a_0+{n-2\choose 0}a_1+\cdots+{0\choose 0}a_{n-1}\\ k=2&a_0&2a_0+a_1&3a_0+2a_1+a_2&\cdots&{n\choose 1}a_0+{n-1\choose 1}a_1+\cdots+{1\choose 1}a_{n-1}\\ k=3&a_0&3a_0+a_1&6a_0+3a_1+a_2&\cdots&{n+1\choose 2}a_0+{n\choose 2}a_1+\cdots+{2\choose 2}a_{n-1}\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\ k=m&a_0&ma_0+a_1&\cdots&\cdots&\cdots \end{matrix} \]

可以发现，操作 \(k\) 次后，\(a_i\) 对 \(a_{n-1}\) 的贡献系数 \(x\) 就是：

\[n-i+k-2\choose k-1 \]

当且仅当 \(n-i+k-2\choose k-1\) 为奇数的时候，\(a_i\) 才能对 \(a_{n-1}\) 产生贡献。由 Lucas 定理，这个条件等价于 \(n-i-1\) 和 \(k-1\) 的按位与是 \(0\)。用 \(U\) 表示全集，集合运算表示位运算，那么这个条件又等价于 \(k-1\subseteq U\setminus (n-i-1)\)。这个玩意就是一个高维后缀和。

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

#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 1e6, LOGN = 20;

int n, m, a[N + 10], b[1 << LOGN];

int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; i++)
    scanf("%d", a + i);
  int all = (1 << LOGN) - 1;
  for (int i = 0; i < n; i++)
    b[all ^ (n - i - 1)] = a[i];
  for (int i = 0; i < LOGN; i++)
    for (int msk = 0; msk < (1 << LOGN); msk++)
      if (!((msk >> i) & 1)) b[msk] ^= b[msk ^ (1 << i)];
  for (int i = 0; i < m; i++)
    printf("%d%c", b[i], " \n"[i == m - 1]);
  return 0;
}

标签：XORs,matrix,int,题解,cdots,Prefix,choose,3a
From： https://www.cnblogs.com/registergen/p/solution_arc137d.html