Cube Or
Time Limit: 2000/2000 MS(Java/Others) Memory Limit: 262144/262144 K(Java/Others)
Problem Description :
Given you N Integers ai (1≤i≤N) , you can do thefollowing operation: pick out one integer, write down the value on a paper,then put this integer back . After you’ve done this operation three times, you dobitwise operation OR to all the three number you have picked. Now you need toanswer q queries. For the ith query, you know the final answer ansi after OR operation. And you need to find how many different ways you cando to get ansi. Two ways are different if in some operation, one way you pick up ai andthe other way you pick up aj and i ≠ j.
Input:
The first line contains 2integers, N (1≤N≤300000) and q (1≤q≤300000) .
The second line contains Nintegers. The ith (1≤i≤N) integer represents ai (0≤ai≤1e6).
The third line contain qintegers. The ith (1≤i≤N) integer represents ansi (0≤ansi≤1e6).
Output:
Output q integers, the ith corresponds to the number of different waysof the ith query.
Sample Input:
10 3
3 3 3 4 5 6 7 8 9 10
3 7 15
Sample Output:
27 301 378
Hint:
There’re 103 = 1000 different of ways topick in total.
For the first query, only choosing from the first 3number can get final answer of 3. So the number of ways to get 3 is 33 =27.
题解：我们将输入的所有数按照其值为下标，统计其出现的次数。要取3个数进行位或，得到q，目标就是求取数的方案数。
样例q = 3的时候，只能取前3个数进行or操作才能得到，由于取出以后可以放回，因此共有3*3*3 = 27种可能。
我们可以这样考虑举个例子，对于要or到(111)2 的情况，我们先统计(111)2的所有子集出现次数的和（这里x子集y的定义就是在x的二进制位取0的情况下y相应的二进制位也必须为0）
那么(111)2的子集有(000)2 ，(001)2，(010)2，(011)2，(100)2，(101)2，(110)2，(111)2 ，那么他们子集出现次数的和为(011)2：3次 ；(100)2：1次；(101)2：1次；(110)2：1次，（111）2:1次，共6次，因此我们定义计算7*7*7 = 343为（111）2的毛方案数，然后我们再从343中减去不满足的情况就好了，那么不满足的情况有什么呢？
不满足的情况就是（111）2的子集 的毛方案数。也就是说（000）2的毛方案数为0；（001）2的毛方案数为0；（010）2的毛方案数为0；（011）2的毛方案数为27,；（100）2的毛方案数为1；(101）2的毛方案数为8；（110）2的毛方案数为8；然后（111）2的净方案数为343-27-1-8-8 = 301这就是第2个样例的计算方案。
因此我们定义动态规划的最优子结构。dp[i][j]表示数字j仅考虑后i位数字时的统计值
转移方程dp[i][j] = dp[i-1][j] + dp[i-1][j^(1<<(i-1))]，前提：j & (1<<(i-1)) != 0 否则的话 直接有 dp[i][j] = dp[i-1][j]
因为dp[i]仅与dp[i-1]有关并且 对于一个确定的i， j^(1<<(i-1))与j不会同时出现，这就保证了我可以减少一维数组，节省空间，并且不会有后效性。
即直接定义dp[j]作为数字j仅考虑后i为数字时的统计值。
求完统计值以后，直接对统计值进行求立方，就可以得到毛方案数了。后面的处理自己看代码吧。代码很简练，我的题解是通过反推南开提供的标准答案得到的。
附上南开大学提供的标准答案：
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll stat[1 << 20]; int n, q; int main() { ios_base::sync_with_stdio(0); for(int I=1;I<=20;I++) { memset(stat,0,sizeof(stat)); char iName[100],oName[100]; sprintf(iName,"data/%d.in",I); sprintf(oName,"data/%d.out",I); freopen(iName,"r",stdin); freopen(oName,"w",stdout); scanf("%d%d", &n, &q); for(int i = 0; i < n; i++) { int num; scanf("%d", &num); stat[num]++; } for(int i = 0; i < 20; i++) { for(int j = 0; j < 1 << 20; j++) if(j & (1 << i)) { stat[j] += stat[j ^ (1 << i)]; } } for(int i = 0; i < 1 << 20; i++) { stat[i] = stat[i] * stat[i] * stat[i]; } for(int i = 0; i < 20; i++) { for(int j = 0; j < 1 << 20; j++) if(j & (1 << i)) { stat[j] -= stat[j ^ (1 << i)]; } } for(int i = 0; i < q; i++) { int num; scanf("%d", &num); cout << stat[num]; if(i != q - 1) cout << ' '; } cout << endl; } return 0; } /* 10 3 3 3 3 4 5 6 7 8 9 10 3 7 15 */
