fork download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 1 << 20;
  4. const int LN = 20;
  5. const int mod1 = 1e9 + 7;
  6. const int mod2 = 1e9 + 9;
  7. int n;
  8. int cnt[N];
  9. int pw1[N];
  10. int pw2[N];
  11. int dp[N][2];
  12. int res1[N];
  13. int res2[N];
  14. void sosdp(){
  15. 	for(int i = 0 ; i < N ; ++i){
  16. 		dp[i][0] = cnt[i];
  17. 	}
  18. 	for(int j = 0 ; j < LN ; ++j){
  19. 		for(int i = 0 ; i < N ; ++i){
  20. 			if(!((i >> j) & 1)){
  21. 				dp[i][0] += dp[i | (1 << j)][0];
  22. 			}
  23. 		}
  24. 	}
  25. 	for(int i = 0 ; i < N ; ++i){
  26. 		res1[i] = pw1[dp[i][0]] - 1;
  27. 		res2[i] = pw2[dp[i][0]] - 1;
  28. 	}
  29. }
  30. void inversesosdp(){
  31. 	for(int i = 0 ; i < N ; ++i){
  32. 		dp[i][0] = res1[i];
  33. 		dp[i][1] = res2[i];
  34. 	}
  35. 	for(int j = 0 ; j < LN ; ++j){
  36. 		for(int i = 0 ; i < N ; ++i){
  37. 			if(!((i >> j) & 1)){
  38. 				dp[i][0] -= dp[i | (1 << j)][0];
  39. 				dp[i][1] -= dp[i | (1 << j)][1];
  40. 				dp[i][0] += (dp[i][0] < 0) * mod1;
  41. 				dp[i][1] += (dp[i][1] < 0) * mod2;
  42. 			}
  43. 		}
  44. 	}
  45. 	for(int i = 0 ; i < N ; ++i){
  46. 		res1[i] = dp[i][0];
  47. 		res2[i] = dp[i][1];
  48. 	}
  49. }
  50. int main(){
  51. 	scanf("%d" , &n);
  52. 	while(n--){
  53. 		int inp;
  54. 		scanf("%d" , &inp);
  55. 		cnt[inp] = 1;
  56. 	}
  57. 	pw1[0] = 1;
  58. 	pw2[0] = 1;
  59. 	for(int i = 1 ; i < N ; ++i){
  60. 		pw1[i] = (pw1[i - 1] * 2) % mod1;
  61. 		pw2[i] = (pw2[i - 1] * 2) % mod2;
  62. 	}
  63. 	sosdp();
  64. 	inversesosdp();
  65. 	int ans = 1;
  66. 	for(int i = 1 ; i < N ; ++i){
  67. 		ans += (res1[i] && res2[i]);
  68. 	}
  69. 	printf("%d\n" , ans);
  70. }
Success #stdin #stdout 0.05s 43912KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/6wJJrZ
language:
C++14 (gcc 8.3)
created:
7 years 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!