HDU 6129 Just do it

/ 0评 / 0

记一次打表没看出规律
Time Limit: 5000/2500 MS (Java/Others)
There is a nonnegative integer sequence $ a_1...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 $ a_1,...,a_i$. 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×10^5,1≤m≤10^9)$.
The second line contains $ n $nonnegative integers $ a_1...n$ $ (0≤a_i≤2^30−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

题解:

这里用到了卢卡斯定理的推论:对于$C_n^m$ 为奇数的充要条件是 $ n \& m == m$
对于变换m次我们考虑每个数的倒数k位数,打表看出倒数第k位数的系数为$ C_{k+m-2}^{k-1}$这样通过推论可以确定奇偶性,由异或性质可判断这个系数对应的数对每个数是否有贡献。另开一个数组$ b$,存贡献。遍历从$ 1~n$,在每次循环中得出倒数第$ i$位数对第$ i$ ~ $ n$个数是否有贡献。

Code:

发表评论

电子邮件地址不会被公开。 必填项已用*标注