<span>QDU69 有趣的异或</span>
<label class="problem-label">描述</label>
这是一个有趣的题，给你n个数，聪明的大家都知道从中挑出k个数的方案数是多少？（ps:当然不会考你这么简单的题）。
现在我们按照如下规则产生A(k)：
1.从n个数中挑出k个数
2.将这k个数作异或运算（S=a1^a2^..ak）
3.将每一种可能的方案产生的S求和
<label class="problem-label">输入</label>
多组测试数据，以EOF结束程序。 每组测试数据第一行包含一个数n（1 <= n <= 1000）. 第二行包含n个数，以空格隔开。保证每个数都在int范围内。
<label class="problem-label">输出</label>
对于每组数据输出一行n个数，以空格隔开，依次表示A(1),A(2)...A(n),行末没有空格。 需要注意的是，输出的结果可能很大，需要对1000003（10^6+3）取余。
<label class="problem-label">样例输入1</label> 复制
4 1 2 10 1
<label class="problem-label">样例输出1</label>
14 36 30 8
乱搞题。 考虑算每一位的贡献，只有当有奇数个1的时候，异或的结果才会是1，这就可以根据这个乱搞一下了。
#include <bits/stdc++.h> using namespace std; int n; int a[10010]; const int mod = 1e6+3; int cnt[33][2]; int c[1010][1010]; void init() { for(int i=0; i<=1000; i++) c[i][0] = 1,c[i][i] = 1; for(int i=1; i<=1000; i++) for(int j=1; j<i; j++) c[i][j] = (c[i-1][j] + c[i-1][j-1])%mod; } int main() { init(); while(cin>>n) { memset(cnt, 0, sizeof(cnt)); for(int i=1; i<=n; i++) scanf("%d", &a[i]); for(int i=1; i<=n; i++) { for(int j=0; j<=30; j++) { if((1<<j)&a[i]) cnt[j+1][1] ++; else cnt[j+1][0] ++; } } for(int i=1; i<=n; i++) { long long ans = 0; for(int j=1; j<=31; j++) { for(int k=1; k<=cnt[j][1]&&k<=i; k+=2) { if(i - k > cnt[j][0]) continue; ans += (((long long)c[cnt[j][1]][k]*c[cnt[j][0]][i-k])%mod)*(1LL<<(j-1)); ans %= mod; } } printf("%lld%s", ans, i==n?"\n":" "); } } return 0; }
投递蚂蚁集团等公司10个岗位 >