题意

有一个长度为 $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$ 位的所有情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
}