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. const int N = 2e5 + 5; 
  12. const int MOD = 1e9 + 7;  
  13.  
  14. void add(int& a, int b) {
  15. 	a += b; 
  16. 	if (a >= MOD) a -= MOD;  
  17. 	if (a < 0) a += MOD;  
  18. }
  19.  
  20. int n;  
  21. int a[N]; 
  22.  
  23. int pow2[N]; 
  24. int sos[1 << 18]; 
  25.  
  26. int sign(int mask) {
  27. 	return (__builtin_parity(mask) ? 1 : -1); 
  28. }
  29.  
  30. int main() {
  31. 	ios::sync_with_stdio(false); 
  32. 	cin.tie(nullptr); 	
  33. 	cin >> n;
  34. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  35.  
  36. 	pow2[0] = 1;  
  37. 	for (int i = 1; i <= n; i++) pow2[i] = 2 * pow2[i - 1] % MOD;  
  38.  
  39. 	for (int i = 1; i <= n; i++) ++sos[a[i]];  
  40.  
  41. 	for (int i = 0; i < 18; i++) {
  42. 		for (int mask = 0; mask < (1 << 18); mask++) {
  43. 			if (!(mask & (1 << i))) sos[mask] += sos[mask ^ (1 << i)]; 
  44. 		}
  45. 	}
  46.  
  47. 	for (int mask = 0; mask < (1 << 18); mask++) {
  48. 		sos[mask] = sign(mask) * (pow2[sos[mask]] - 1); 
  49. 	}
  50.  
  51. 	for (int i = 0; i < 18; i++) {
  52. 		for (int mask = 0; mask < (1 << 18); mask++) {
  53. 			if (!(mask & (1 << i))) add(sos[mask], sos[mask ^ (1 << i)]); 
  54. 		}
  55. 	}
  56.  
  57. 	for (int mask = 0; mask < (1 << 18); mask++) {
  58. 		sos[mask] = sign(mask) * sos[mask]; 
  59. 		if (sos[mask] < 0) sos[mask] += MOD;
  60. 	}
  61.  
  62. 	for (int k = 0; k <= n; k++) {
  63. 		cout << sos[k] << ' '; 
  64. 	}
  65. }
Success #stdin #stdout 0.02s 5288KB
comments (?)
stdin
copy 
4
3 1 3 4
stdout
copy 
7 4 0 3 1
https://ideone.com/eOB7Rh
language:
C++14 (gcc 8.3)
created:
12 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!