Just do it

Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 299    Accepted Submission(s): 171 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

题目大意：

设定b【i】=a【1】^a【2】^a【3】^..................a【i】；

每进行一次，我们可以从a数组得到一个b数组。问进行m次的结果。

思路：

我们随手写下四项的前两次结果，不难看出，我们设定ans【i】【j】表示进行到第i次，第j个位子的答案的话，ans【i】【j】有推导式：

ans【i】【j】=ans【i-1】【j】^ans【i】【j-1】；

那么很显然，对于每一项，他的系数就是杨辉三角的值，那么如果当前位子系数为奇数的话，结果就会有贡献。

同样很显然，我们第i行，第j列的答案，其系数为C（i+j-2，j-1）【此时只考虑a的系数】；

那么我们只需要考虑第一项（a）对所有位子的结果的影响即可（因为b就相当于向后挪了一下递推即可）。

那么根据上述公式，考虑第一项（a）对所有位子的结果的影响然后递推一下就行了。

Ac代码：

[cpp] view plain copy print ? #include<stdio.h>  #include<string.h>  using namespace std;  int a[2050000];  int b[2050000];  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<=n;i++)          {              int y=i-1;              int x=i+m-2;              if((x&y)==y)              {                  for(int j=i;j<=n;j++)b[j]^=a[j-i+1];              }          }          for(int i=1;i<=n;i++)          {              if(i>1)printf(" ");              printf("%d",b[i]);          }          printf("\n");      }  }   #include<stdio.h> #include<string.h> using namespace std; int a[2050000]; int b[2050000]; 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<=n;i++) { int y=i-1; int x=i+m-2; if((x&y)==y) { for(int j=i;j<=n;j++)b[j]^=a[j-i+1]; } } for(int i=1;i<=n;i++) { if(i>1)printf(" "); printf("%d",b[i]); } printf("\n"); } }