欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Just do it(HDU 6129)

程序员文章站 2024-03-23 20:49:10
...

Just do it

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


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(1T5), denoting the number of test cases.
For each test case:
The first line contains two positive integers n,m(1n2×105,1m109).
The second line contains n nonnegative integers a1...n(0ai2301).
 

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
 

//题意有一个长度为nn的整数序列{a_n}{an},对其做mm次前缀异或和,求最终的序列。

//思路

        a1         a2               a3                   a4                          a5   
1:  a1       a1^a2       a1^a2^a3     a1^a2^a3^a4       a1^a2^a3^a4^a5

2:  a1         a2             a1^a3             a2^a4                   a1^a3^a5

3:  a1       a1^a2         a2^a3             a3^a4                   a1^a4^a5
 
4:    a1         a2                a3                  a4                          a1^a5

......

可以看出a[k]对a[i](i>=k)的影响就2种情况,要么^a[k],要么没影响,因为异或偶数个相同的数相当于异或0。所以我们只要算每个a[i]对答案b[i]的贡献,贡献了奇数次则^a[i],否则就贡献了0。

第i次a[1]对其他a[]的贡献次数
1: 1     1     1     1     1
2: 1     2     3     4     5
3: 1     3     6     10   15
4: 1     4     10   20   35
5: 1     5     15   35   70
......

a[2]、a[3]、a[4]、...、a[n] 同 。

可以看出斜三角都成杨辉三角,而对于杨辉三角,第x次变换第y项是C(x+y-2,y-1)

根据Lucas定理,C(a,b)是奇数当且仅当把a,b二进制表达后b中1的位置是a中1的位置的子集。

 a&b==b 。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX = 2e5 + 100;
int a[MAX];
int val[MAX];

int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		memset(val, 0, sizeof(val));
		for (int i = 1; i <= n; i++)
		{
			scanf("%d", &a[i]);
		}
		for (int i = 1; i <= n; i++)
		{
			int x = m + i - 2;
			int y = i - 1;
			//必须加(),"&"优先级比"=="低
			if ((x&y) == y)
			{
				for (int j = i; j <= n; j++)
					val[j] ^= a[j - i + 1];
			}
		}
		for (int i = 1; i < n; i++)
		{
			printf("%d ", val[i]);
		}
		printf("%d\n", val[n]);
	}
	return 0;
}