首页 > 代码库 > hdu 5244 inverse（分治）
hdu 5244 inverse（分治）
inverse
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 193 Accepted Submission(s): 97
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(0≤i<n) be the i-th number of this original array.
Let bi(0≤i<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.
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.
The array is encrypted as follows.
Let ai(0≤i<n) be the i-th number of this original array.
Let bi(0≤i<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=∑0≤j<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(T≤5), denoting the number of the test cases.
For each test case, the first line contains an integer k(0≤k≤20),
The next line contains n=2k integers, which are bi respectively.
It is guaranteed that, ai is an integer and 0≤ai≤109.
For each test case, the first line contains an integer k(0≤k≤20),
The next line contains n=2k integers, which are bi respectively.
It is guaranteed that, ai is an integer and 0≤ai≤109.
Output
For each test case, output ‘‘Case #t:‘‘ to represent this is the t-th case. And then output the array a.
Sample Input
2023325 3 4 10
Sample Output
Case #1: 233Case #2: 1 2 3 4
Source
The 2015 ACM-ICPC China Shanghai Metropolitan Programming Contest
Recommend
hdu 5244 inverse（分治）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。