2017 Multi-University Training Contest

http://acm.hdu.edu.cn/showproblem.php?pid=6129

题意：一次操作就是i从1~n有 A[i]=A[i]^A[i-1]^A[i-2]...^A[1] 那么这样操作m次会得到什么

解法：

我们先打一个表

5 10
1 2 3 4 5
1 3 0 4 1
1 2 2 6 7
1 3 1 7 0
1 2 3 4 4
1 3 0 4 0
1 2 2 6 6
1 3 1 7 1
1 2 3 4 5
1 3 0 4 1
1 2 2 6 7
我们看出...1 2和1 2 3和1 2 3 4会在某一次进行保留，比如10次操作会保留1 2两个数..
于是大胆的想法：保留的数字个数和m&(-m)==ans有关
那么剩下的数字呢，第三个数字2是有1^3得到的，第四个数字是2^4得到的，于是大胆的想法A[i]=A[i]^A[i-ans]
于是就按照大胆的想法写，接下来m-ans继续来一次

#include<bits/stdc++.h>
using namespace std;
int mp[1010];
int x[423456];
int n,m;
int sum;
map<int,int>Ma,Mp;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            scanf("%d",&x[i]);
        }
        while(m){
            int ans=m&(-m);
            for(int i=ans+1;i<=n;i++){
                x[i]^=x[i-ans];
            }
            m-=ans;
        }
        for(int i=1;i<=n;i++){
            if(i==n){
                printf("%d
",x[i]);
            }else{
                printf("%d ",x[i]);
            }
        }
    }
    return 0;
}