[HDU 4810] Wall Painting 组合数 按位处理

Wall Painting

Time Limit: 5000ms Memory Limit: 32MB

Description

Ms.Fang loves painting very much. She paints GFW(Great Funny Wall) every day. Every day before painting, she PRoduces a wonderful color of pigments by mixing water and some bags of pigments. On the K-th day, she will select K specific bags of pigments and mix them to get a color of pigments which she will use that day. When she mixes a bag of pigments with color A and a bag of pigments with color B, she will get pigments with color A xor B. When she mixes two bags of pigments with the same color, she will get color zero for some strange reasons. Now, her husband Mr.Fang has no idea about which K bags of pigments Ms.Fang will select on the K-th day. He wonders the sum of the colors Ms.Fang will get with C(N,K) different plans.

For example, assume n = 3, K = 2 and three bags of pigments with color 2, 1, 2. She can get color 3, 3, 0 with 3 different plans. In this instance, the answer Mr.Fang wants to get on the second day is 3 + 3 + 0 = 6. Mr.Fang is so busy that he doesn’t want to spend too much time on it. Can you help him? You should tell Mr.Fang the answer from the first day to the n-th day.

Input

There are several test cases, please process till EOF. For each test case, the first line contains a single integer N(1 <= N <= 10 3).The second line contains N integers. The i-th integer represents the color of the pigments in the i-th bag.

Output

For each test case, output N integers in a line representing the answers(mod 10 6 +3) from the first day to the n-th day.

Sample Input

4 1 2 10 1

Sample Output

14 36 30 8

题目大意

给N个数，对所有1<=i<=N，求从N个数中选择i个数异或起来的所有方案异或值累和。

解题报告

很少做数学题，寒假回来神犇就送了五道数论要求一次AC的考试大礼包，果断爆0。 感觉数学太差了，所以写点数学的博客。。。。

考虑选i个的情况，首先发现如果要异或的话，二进制下单个数位位之间不影响，可以对二进制每一位分别考虑，问题就简单多了。 考虑第K位，加入N个数中第K位为1的数有cnt[K]个，因为第K位为零的数不产生任何影响，第K位为一的数选中个数为奇数个才不为0，所以枚举选取第K位为一的数j个,j=1,3,5….(j<=cnt[K] && j<=i)。 这种情况下 选择第K位为零的数的方案数为C(N-j, i-j) 选择第K位为一的数的方案数为C(cnt[K], j) 那么总方案数就是他们的乘积，对sum的贡献为C(N−j,i−j)∗C(cnt[K],j)∗2k−1 $$C(N-j, i-j)*C(cnt[K], j)*2^{k-1}$$ 然后就发现时间复杂度为O(N2)$O(N^2)$加上一个32的常数还有多组测试数据，5秒有点悬啊 别管那么多啦反正大力出奇迹就对啦0.0

代码