fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. int L, q;  
  12. int toxic[1 << 20]; 
  13.  
  14. int sos_sub[1 << 20], sos_super[1 << 20];
  15.  
  16. int main() {
  17. 	ios::sync_with_stdio(false); 
  18. 	cin.tie(nullptr); 	
  19. 	cin >> L >> q; 
  20. 	for (int i = 0; i < (1 << L); i++) {
  21. 		char c; cin >> c; 
  22. 		toxic[i] = c - '0'; 
  23. 	}	
  24.  
  25. 	for (int mask = 0; mask < (1 << L); mask++) {
  26. 		sos_sub[mask] = sos_super[mask] = toxic[mask];
  27. 	}
  28.  
  29. 	for (int i = 0; i < L; i++) {
  30. 		for (int mask = 0; mask < (1 << L); mask++) {
  31. 			if (mask & (1 << i)) sos_sub[mask] += sos_sub[mask ^ (1 << i)];
  32. 			else sos_super[mask] += sos_super[mask ^ (1 << i)];
  33. 		}
  34. 	}
  35.  
  36. 	while (q--) {
  37. 		string t; cin >> t; 
  38. 		reverse(t.begin(), t.end());  
  39.  
  40. 		int mask_z = 0, mask_o = 0, mask_q = 0;  
  41. 		for (int i = 0; i < L; i++) {
  42. 			if (t[i] == '0') mask_z |= (1 << i);  
  43. 			if (t[i] == '1') mask_o |= (1 << i);  
  44. 			if (t[i] == '?') mask_q |= (1 << i);
  45. 		}
  46.  
  47. 		int ans = 0; 
  48. 		if (__builtin_popcount(mask_q) <= 6) {
  49. 			ans = toxic[mask_o];   
  50. 			for (int sub = mask_q; sub > 0; sub = (sub - 1) & mask_q) {
  51. 				ans += toxic[sub | mask_o];
  52. 			}
  53. 		}
  54. 		else if (__builtin_popcount(mask_o) <= 6) {
  55. 			ans = (__builtin_parity(mask_o) ? -1 : 1) * sos_sub[mask_q];
  56. 			for (int sub = mask_o; sub > 0; sub = (sub - 1) & mask_o) {
  57. 				int sign = __builtin_parity(sub) ^ __builtin_parity(mask_o) ? -1 : 1;
  58. 				ans += sign * sos_sub[sub | mask_q];
  59. 			}
  60. 		}
  61. 		else {
  62. 			ans = sos_super[mask_o]; 
  63. 			for (int sub = mask_z; sub > 0; sub = (sub - 1) & mask_z) {
  64. 				int sign = __builtin_parity(sub) ? -1 : 1;
  65. 				ans += sign * sos_super[sub | mask_o];
  66. 			}
  67. 		}
  68.  
  69. 		cout << ans << '\n';
  70. 	}
  71. }
Success #stdin #stdout 0.01s 7688KB
comments (?)
stdin
copy 
3 5
12345678
000
0??
1?0
?11
???
stdout
copy 
1
10
12
12
36
https://ideone.com/AVHmyY
language:
C++14 (gcc 8.3)
created:
11 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!