HDU 6129 Just do it （组合数）

HDU 6129 Just do it （组合数）

Description

There is a nonnegative integer sequence a1…n of length n. HazelFan wants to do a type of transformation called prefix-XOR, which means a1…n changes into b1…n, where bi equals to the XOR value of a1,…,ai. He will repeat it for m times, please tell him the final sequence.

Input

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases.For each test case:The first line contains two positive integers n,m(1≤n≤2×10^5,1≤m≤10^9).The second line contains n nonnegative integers a1…n(0≤ai≤2^30−1).

Output

For each test case:A single line contains n nonnegative integers, denoting the final sequence.

Sample Input

21 113 31 2 3

Sample Output

11 3 1

题意

有一个长度为 n 的整数序列 {an}

思路

可以发现做 m 次后，位置为 x 的初始值对位置为 y 的最终值的贡献次数是一个只和 m 与 y-x 相关的组合式，而我们只关注这个次数的奇偶性。考虑 Lucas 定理， (ba)

容易得出，该组合数的计算公式为 (m+i−2i−1) ，其中 m 已知，枚举所有的 i ，当 (i−1)&(m+i−2)==(i−1) 时即说明该组合数的结果为奇数，则每一项对与其间隔为 i$i$ 的数字有所贡献，统计更新即可。

AC 代码

#includeusing namespace std;const int maxn = 2e5+10;int a[maxn], b[maxn];int main(){ int t; scanf("%d", &t); while(t--) { int n,m; scanf("%d%d", &n, &m); memset(b,0,sizeof(b)); for(int i=1; i<=n; i++) scanf("%d", &a[i]); for(int i=1; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。