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(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).
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.
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
//题意:有一个长度为n的整数序列{an},对其做m次前缀异或和,求最终的序列。
//思路:
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;
}
上一篇: do...while(0) 的妙用
下一篇: java 控制台输入