fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define el '\n'
  6. #define TASK ""
  7. #define int long long
  8. #define MASK(n) (1LL << (n))
  9.  
  10. const int MAXN = 1e5 + 5;
  11. const int MOD = 1e9 + 7;
  12.  
  13. int n;
  14. int a[MAXN];
  15. bool isPrime[75];
  16. vector <int> prime;
  17. vector <int> dp;
  18. vector <int> n_dp;
  19. map <int , int> ap;
  20.  
  21. void Sieve(){
  22. 	for(int i = 2 ; i <= 70 ; i ++){
  23. 		if (! isPrime[i]){
  24. 			prime.push_back(i);
  25. 			for(int j = i * i ; j <= 70 ; j += i){
  26. 				isPrime[j] = 1;
  27. 			}
  28. 		}
  29. 	}
  30. }
  31.  
  32. int modPow(int base, int exp){
  33.     int res = 1;
  34.     while(exp){
  35.         if(exp & 1) res = res * base % MOD;
  36.         base = base * base % MOD;
  37.         exp >>= 1;
  38.     }
  39.     return res;
  40. }
  41.  
  42. signed main(){
  43. 	if (fopen(TASK".inp" , "r")){
  44.     	freopen(TASK".inp" , "r" , stdin); 
  45.     	freopen (TASK".out" , "w" , stdout); 
  46. 	}
  47.  
  48.     ios_base::sync_with_stdio(false);
  49. 	cin.tie(NULL);
  50.  
  51. 	Sieve();
  52.  
  53. 	cin >> n;
  54.  
  55. 	int sz = prime.size();
  56.  
  57. 	dp.assign(MASK(sz) , 0);
  58. 	n_dp.assign(MASK(sz) , 0);
  59.  
  60. 	for(int i = 1 ; i <= n ; i ++){
  61. 		int x;
  62. 		cin >> x;
  63. 		int mask = 0 , v = x;
  64. 		for(int j = 0 ; j < sz ; j ++){
  65. 			int cnt = 0;
  66. 			while(v % prime[j] == 0){
  67. 				v /= prime[j];
  68. 				cnt ^= 1;
  69. 			}
  70. 			if (cnt) mask |= MASK(j);
  71. 		}
  72. 		ap[mask] ++;
  73. 	}
  74.  
  75. 	dp[0] = 1;
  76.  
  77. 	for(auto x : ap){
  78. 		int f = x.second;
  79. 		int way = modPow(2 , f - 1);
  80. 		int even = way , odd = way;
  81. 		fill(n_dp.begin() , n_dp.end() , 0);
  82. 		for(int mask = 0 ; mask < MASK(sz) ; mask ++){
  83. 			if (dp[mask] != 0){
  84. 				int cur = dp[mask];
  85. 				n_dp[mask] = (n_dp[mask] + cur * even) % MOD;
  86. 				int mask2 = mask ^ x.first;
  87. 				n_dp[mask2] = (n_dp[mask2] + cur * odd) % MOD;
  88. 			}
  89. 		}
  90. 		dp.swap(n_dp);
  91. 	}
  92.  
  93. 	cout << (dp[0] - 1 + MOD) % MOD;
  94.  
  95.     return 0;
  96. }
  97.  
  98. /*
  99. ⠀⠀⠀⠀⠀⠀⢀⡤⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡀
  100. ⠀⠀⠀⠀⠀⢀⡏⠀⠀⠈⠳⣄⠀⠀⠀⠀⠀⣀⠴⠋⠉⠉⡆
  101. ⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠈⠉⠉⠙⠓⠚⠁⠀⠀⠀⠀⣿
  102. ⠀⠀⠀⠀⢀⠞⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣄
  103. ⠀⠀⠀⠀⡞⠀⠀⠀⠀⠀⠶⠀⠀⠀⠀⠀⠀⠦⠀⠀⠀⠀⠀⠸⡆
  104.  
  105.  
  106. 									*/
  107.  
Success #stdin #stdout 0.01s 11484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/d8q8vO
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

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!