Just do it(规律+技巧+总是时间超限)

本文主要是介绍Just do it(规律+技巧+总是时间超限)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：http://acm.hdu.edu.cn/showproblem.php?pid=6129
题目：Just do it

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

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

思路：这个题目真的让我感觉自己有多么弱，这次比赛也是这样的，心累。发现自己很多知识不会。之前做的时候，还把规律找错了，最关键的时候队友找出来的规律是每个数友有相应的周期，比如：3的周期是4,4的周期是4,N为（5到8）的时候，周期是8.但是这个并没有什么用，周期还是太大了。比完之后，看到了别人的题解，竟然可以联想到杨辉三角，还能找出这样规律，真是佩服。还有一个自己不知道德知识点：C(n,m)的结果如果是奇数的话，那么（n|m）=m.(这个自己找资料区了解，跟Lucas定理有关)，下面是别人的做法。
我们随手写下四项的前两次结果，不难看出，我们设定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）对所有位子的结果的影响然后递推一下就行了

别人的代码：

#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<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){int t,n,m;int a[200001];int b[200001];scanf("%d",&t); int x,y;int i,j;while(t--){scanf("%d%d",&n,&m);for(i=0;i<n;i++){scanf("%d",&a[i]);//不要用cin输入 }memset(b,0,sizeof(b));//注意一定要初始化 for(i=0;i<n;i++){x=i;y=m+i-1;//注意我这里i=0开始的。 if((x&y)==x){for(j=i;j<n;j++){b[j]^=a[j-i];//相当于递归，把前面的每一项当做第一项，然后用那个规律，这样比每一次吧那一项算完省时。 }}}cout<<b[0];for(i=1;i<n;i++){cout<<' '<<b[i];}cout<<endl;}return 0;
}