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 = 1e5 + 5; 
  12. const int MAX_A = 70; 
  13. const int MOD = 1e9 + 7;   
  14.  
  15. int prime[19] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}; 
  16.  
  17. void add(int& a, int b) {
  18. 	a += b; 
  19. 	if (a >= MOD) a -= MOD; 
  20. 	if (a < 0) a += MOD; 
  21. }
  22.  
  23. int binpow(int a, int b) {
  24. 	int ans = 1; 
  25. 	for (; b > 0; b >>= 1) {
  26. 		if (b & 1) ans = 1ll * ans * a % MOD;  
  27. 		a = 1ll * a * a % MOD; 
  28. 	}
  29. 	return ans;
  30. }
  31.  
  32. int n;  
  33. int a[N];
  34. int cnt[MAX_A + 5]; // cnt[x] = số lần xuất hiện của giá trị x
  35.  
  36. // mask đại diện cho tính chẵn lẻ của các số mũ của một tập hợp số nguyên tố, trong đó: 
  37. // bit thứ i là 1: số nguyên tố thứ i xuất hiện lẻ lần hay có số mũ lẻ
  38. // bit thứ i là 0: số nguyên tố thứ i xuất hiện chẵn lần hay có số mũ chẵn
  39.  
  40. int prime_mask[MAX_A + 5]; // prime_mask[x] = mask tương ứng với tập ước nguyên tố của x
  41. int dp[MAX_A + 5][1 << 19]; // dp[x][mask] = Số tập hợp khác nhau khi xét các giá trị từ 1 đến x,
  42. 							// với mask tương ứng với tập ước nguyên tố của tích của tập hợp
  43.  
  44. int main() {
  45. 	ios::sync_with_stdio(false); 
  46. 	cin.tie(nullptr); 	
  47. 	cin >> n; 
  48. 	for (int i = 1; i <= n; i++) {
  49. 		cin >> a[i];
  50. 		cnt[a[i]]++; 
  51. 	} 
  52.  
  53. 	for (int x = 1; x <= MAX_A; x++) {
  54. 		int tmp = x;  
  55. 		for (int i = 0; i < 19; i++) {
  56. 			int e = 0;   
  57. 			while (tmp % prime[i] == 0) {
  58. 				tmp /= prime[i]; 
  59. 				e += 1; 
  60. 			}
  61. 			if (e & 1) prime_mask[x] |= (1 << i); 
  62. 		}
  63. 	}
  64.  
  65. 	dp[0][0] = 1; 
  66. 	for (int x = 0; x < MAX_A; x++) {
  67. 		for (int mask = 0; mask < (1 << 19); mask++) {
  68. 			if (dp[x][mask] == 0) continue; 
  69. 			if (cnt[x + 1] == 0) {
  70. 				add(dp[x + 1][mask], dp[x][mask]); 
  71. 			}
  72. 			else {
  73. 				// thêm vào tập hợp hiện tại chẵn phần tử có giá trị là x + 1
  74. 				add(dp[x + 1][mask], 1ll * dp[x][mask] * binpow(2, cnt[x + 1] - 1) % MOD);
  75. 				// thêm vào tập hợp hiện tại lẻ phần tử có giá trị là x + 1
  76. 				add(dp[x + 1][mask ^ prime_mask[x + 1]], 1ll * dp[x][mask] * binpow(2, cnt[x + 1] - 1) % MOD); 
  77. 			}
  78. 		}
  79. 	}
  80.  
  81. 	int ans = dp[MAX_A][0]; 
  82. 	add(ans, -1); // trừ đi trường hợp tập rỗng 
  83.  
  84. 	cout << ans << '\n'; 
  85. }
Success #stdin #stdout 0.03s 5280KB
comments (?)
stdin
copy 
5
1 2 4 5 8
stdout
copy 
7
https://ideone.com/wo4N3u
language:
C++14 (gcc 8.3)
created:
1 year 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!