HDU6129-Just do it

Just do it

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 1205 Accepted Submission(s): 704

Problem 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×105,1≤m≤109).
The second line contains n nonnegative integers a1…n(0≤ai≤230−1).

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

Sample Input

2
1 1
1
3 3
1 2 3

Sample Output

1
1 3 1

Source
2017 Multi-University Training Contest - Team 7

题目大意：给出n个数，进行m次前缀异或和操作，问最后的结果是多少？
解题思路：

$$\begin{align*} & 1\;1\\ & 1\;2 \;1\\ & 1\;3\;6\;1\\ & 1\;4\;10\;20\;1\\ \end{align*}$$
斜地看就是一个杨辉三角，从 $1$开始标号的话，第$i$行第 $j$列的数是$C_{i+j-2}^{j-1}$,第 $k$个数对第$m$行第 $j$列的贡献就是第$k+1$个数对 $m$行第$j+1$列的贡献，贡献为奇数时才记，组合数 $C_{n}^{m}$为奇数的条件为 $n\&m==m$。

#include<iostream>
#include<cstdio>
#include<string>
#include<cmath>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN=2e5+5;
const int MOD=1e9+7;
int a[MAXN],b[MAXN];

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

/*
2
1 1
1
3 3
1 2 3
*/