ARC137D Prefix Xors

pengyule · 2022-11-23 22:15:32 · 题解

首先显然每一位独立，问题变成 01 串的问题。这时如果没有思路，可以考虑找规律，然后发现 k 每 2^{\lceil\log_2 n\rceil} 答案循环一次。而通过打表的一些信息我们又自然而然地想到背后是什么让 01 序列发生如此变化，直觉告诉我们肯定跟 FWT 有些关系。如果运气很好的话，确可找到规律，就是把下标为 [1,n] 的原序列平移到下标为 [2^{\lceil\log_2 n\rceil}-n+1,2^{\lceil\log_2 n\rceil}] 处，然后对 [1,2^{\lceil\log_2 n\rceil}] 做一次 FWT。我运气没这么好，还差那么一点。

另一个直接的思路是看到多次前缀（异或）和便使用路径计数优化 DP（UER#11 切割冰片使用了此方法），那么 a^0_i 对 a^k_n 的贡献就是 {n-i+k-1\choose n-i}a_i^0。
乍一看这个好像跟异或拉不上关系，实际上顺着想下去会发现由于异或是不进位加法，所以实际上贡献就是 \left({n-i+k-1\choose n-i}\bmod 2\right)a_i^0，前者为 1 的充要条件：应用 Lucas 定理得到，\forall b_1，n-i+k-1 的第 b_1 位 \ge n-i 的第 b_1 位，也就是 n-i\subseteq n-i+k-1。

结合图示可知，(n-i+k-1)-(n-i) 与原来 n-i 没有交集，即 k-1 与 n-i 没有交集，k-1\subseteq \complement_U (n-i)，那么 (k-1)\bmod n\subseteq \complement_U(n-i)\bmod n，在 [0,n] 内求 FWT 即可（+ 改为 \oplus）。

#include <bits/stdc++.h>
using namespace std;
int a[2000005],ans[2000005];
int main(){
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    reverse(a+1,a+n+1);
    int nn=ceil(log2(n));n=1<<nn;
    reverse(a+1,a+n+1);
    for(int w=1;w<n;w<<=1)
        for(int i=1;i<=n;i+=w<<1)
            for(int j=i;j<(i+w);j++)
                a[j]^=a[j+w];
    for(int i=0;i<m;i++)cout<<a[i%n+1]<<' ';
}