Just do it

Posted on | In , ,

题目链接

题意

对一个求m次前缀异或和，求这个数列。

思路

我们找一下规律，发现将这个东西列出来之后，对角线上的数字都是组合数。不同数字产生贡献的位置是这些组合数为奇数的位置。
那么我们可以去计算这些组合数是奇数还是偶数，如果为奇数，那么所有数字都会对对应偏移位置产生贡献。
怎么计算一个很大的组合数是奇是偶呢？介绍两种方法。
可以把它拆成阶乘的形式，分别计算分子分母有多少个2因子，相减一下。
也可以考虑模2情况下的卢卡斯定理，变成分解其二进制。
两种方法复杂度均为.

Code

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>
void read(T& ret)
{
	ret = 0;
	char c;
	while ((c = getchar()) > '9' || c < '0');
	while (c >= '0' && c <= '9')
	{
		ret = ret * 10 + c - '0';
		c = getchar();
	}
}
const ll mod = 1e9 + 7;

ll calc(ll n)
{
	ll sum = 0;
	while (n > 1)
	{
		sum += n / 2;
		n /= 2;
	}
	return sum;
}
const int N = 2e5 + 5;
int a[N];
int ans[N];
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int n;
		ll m;
		read(n);
		read(m);
		for(int i=1;i<=n;i++) ans[i]=0;
		for (int i = 1; i <= n; i++)
			read(a[i]);
		for(int i=1;i<=n;i++){
			ans[i]^=a[i];
		}
		for(int i=2;i<=n;i++){
			ll tmp1=i+m-2;
			ll tmp2=i-1;
			ll tmp3=m-1;
			tmp1=calc(tmp1);
			tmp2=calc(tmp2);
			tmp3=calc(tmp3);
			if(tmp1==tmp2+tmp3){
				for(int j=0;j+i<=n;j++){
					ans[j+i]^=a[j+1];
				}
			}
		}
		for(int i=1;i<=n;i++) printf("%d%c",ans[i],i==n?'\n':' ');
	}
	return 0;
}
0%