HDU 6129 lucas判定組合せ数パリティ
2557 ワード
Just do it
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 1106 Accepted Submission(s): 641
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
Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 1106 Accepted Submission(s): 641
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
能A的代码都是从da[i]对答案的贡献的角度去考虑的 实际上的复杂度也是o(n2) 其实正着去推的复杂度也是o(n2) 不知道为什么后者就过不去 而且时间会长很多很多。
不过这也给了我教训 考虑问题要从多个角度去考虑.
注意判断组合数的奇偶性 (a&b)==b那么 C(a,b)就是奇数 另外 注意 &运算优先级低于==运算
#include
#include
#include
#include
#include
#include