亟隐

朝不闻道,夕亦死可矣

05/28
23:27
算法区

HDU 5244 inverse

地址:戳这里

Problem Description

Mike has got a huge array b, and he is told that the array is encrypted.

The array is encrypted as follows.

Let ai(0i<n) be the i-th number of this original array.

Let bi(0i<n) be the i-th number of this encrypted array.

Let n be a power of 2, which means n=2k.

The bi is calculated as following.

bi=0j<nf((i or j) xor i)aj

f(x) means, if the number of 1 in the binary of x is even, it will return 1, otherwise 0.

Mike want to inverse the procedure of encryption.

Please help him recover the array a with the array b.

Input

The first line contains an integer T(T5), denoting the number of the test cases.

For each test case, the first line contains an integer k(0k20),
The next line contains n=2k integers, which are bi respectively.

It is guaranteed that, ai is an integer and 0ai109.

Output
For each test case, output ”Case #t:” to represent this is the t-th case. And then output the array a.
Sample Input
2 0 233 2 5 3 4 10
Sample Output
Case #1: 233 Case #2: 1 2 3 4
Source

 

打印一个矩阵,(i,j)为f((i or j)xor i),就会发现矩阵平均分成四块,就是
A  A^1
A  A
其中每一个A都可以分成这样四个矩阵。如果f((i or j)xor i)换成f((i or j)xor i)*a[j],那么第i行的和就是b[i]。根据矩阵特性可以处理成前面一半的b[]只包含前一半的a[],后一半的b[]只包含后一半的a[]。也就是四个矩阵中只留下左上角和右下角,其他都变成了0,然后递归分治。

代码:戳这里