HDU6129-Just do it-CSDN博客

本文链接：https://blog.csdn.net/a664607530/article/details/77243311

Just do it

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

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

Sample Output

Source

2017 Multi-University Training Contest - Team 7

题意：有n个数，每经过一轮，就对前缀做一次异或，求出最终的序列

解题思路：我们可以找出经过每一轮后的每个数字是由哪些数字异或得到的，比如对于题目中给出的a[1]，我们可以找出经过每一轮后哪些数字是由它异或得到的，后面的数字就是将这个表往右移一位

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <unordered_map>
#include <functional>

using namespace std;

const int INF=0x3f3f3f3f;
#define LL long long

int ans[200009],a[200009];

int dfs(int x,int y,int len)
{
    if(x>len/2&&y>len/2) return 0;
    if(x==1||y==1) return 1;
    if(x>len/2) return dfs(x-len/2,y,len/2);
    else if(y>len/2) return dfs(x,y-len/2,len/2);
    else return dfs(x,y,len/2);
}

int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        memset(ans,0,sizeof ans);
        int k=2;
        while(k<n) k*=2;
        m%=k;
        if(!m) m=k;
        for(int i=1;i<=n;i++)
        {
            if(dfs(m,i,k))
            {
                for(int j=i;j<=n;j++)
                    ans[j]^=a[j-i+1];
            }
        }
        int flag=0;
        for(int i=1;i<=n;i++)
        {
            if(flag) printf(" ");
            else flag=1;
            printf("%d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}