hdu 6129 Just do it

题意

有一个长度为 $n$ 的整数序列 ${a_n}$，对其做 $m$ 次前缀异或和，求最终的序列。

题解

对这个过程手动模拟几行，注意不要消去，可以发现第 $m$ 次第 $i$ 个数的结果包含了 $C_{m-1+i-j}^{i-j}$ 次第 $j$ 个数($j\le i$) 。

首先我们需要判断它的奇偶性。奇偶性相当于2进制的结果，2为质数，可以使用Lucas定理。2进制的每一位只有四种情况，其中 $C_{0}^{1}=0，C_{0}^{0}=C_{1}^{0}=C_{1}^{1}=1$ 。

将 $m-1$ 和 $i-j$ 的每一位展开，在第 $k$ 位上，如果 $m-1$ 和 $i-j$ 都是 1，那么结果就是 0 。

从小到大枚举 $k$ ，表示 $i-j$ 的第 $k$ 位为 1，若 $m-1$ 的第 $k$ 位不为 1，那么直接更新a序列本身。也就是说，每次只用满足 $i-j=2^{k}$ 的 $a[j]$ 更新 $a[i]$，然而此时的 $a[j]$ 已经被 $k$ 取 $0\dots k-1$ 更新过了，所以相当于考虑了 $i-j$ 在 $0\dots k$ 位的所有情况。

代码

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

const int N=2e5+5;
int a[N];

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