Cube Or

Time Limit: 2000/2000 MS(Java/Others)????Memory Limit: 262144/262144 K(Java/Others)

?

Problem Description : ??? ???????? ???????? ???????? ???????? ???????? ????????

Given you N Integers a_i (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 ans_i after OR operation. And you need to find how many different ways you cando to get ans_i. Two ways are different if in some operation, one way you pick up a_i andthe other way you pick up a_j 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 a_i (0≤a_i≤1e6).

The third line contain qintegers. The ith (1≤i≤N) integer represents ans_i (0≤ans_i≤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 10³ = 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 3³ =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 */

總結

以上是生活随笔為你收集整理的Cube Or 北方大学生训练赛的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。