HDU

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

InputThe first line contains a positive integer T(1≤T≤5) 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 ) n,m(1≤n≤2×105,1≤m≤109) .
The second line contains n n nonnegative integers a 1...n (0≤a i ≤2 30 −1) a1...n(0≤ai≤230−1) .
OutputFor each test case:
A single line contains n n nonnegative integers, denoting the final sequence.Sample Input

2
1 1
1
3 3
1 2 3

Sample Output

1
1 3 1

题意：给定a数组，现在有a数组可以转化为b数组，bi=a1^a2^..ai，即b为a数组的异或前缀和；求进行M次后b数组。

思路：暴力每个数对每个位置的贡献：现考虑a[1]对b[i]的贡献，如果是偶数是贡献则可以忽略，而奇数的情况是(i+M-2)&(i-1)==(i-1)（根据杨辉三角）。

如果a[1]对b[i]有贡献，那a[2]对b[i+1]，a[3]对b[i+2]...也有贡献，暴力累计即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=2000010;
int a[maxn],b[maxn];
int main()
{
    int T,N,M;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&N,&M);
        rep(i,1,N) scanf("%d",&a[i]),b[i]=0;
        rep(i,1,N){
            int x=i+M-2,y=i-1;
            if((x&y)==y)
              rep(j,i,N) b[j]^=a[j-i+1];
        }
        rep(i,1,N-1) printf("%d ",b[i]);
        printf("%d
",b[N]);
    }
    return 0;
}