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. // - Tính chất của số chính phương: 
  12. //   Khi phân tích một số chính phương thành các thừa số nguyên tố thì số mũ của mỗi thừa số nguyên tố đều là số chẵn.
  13. // - Có max{a(i)} <= 70 => Chỉ có 19 số nguyên tố <= 70
  14. // => mask biểu diễn tính chẵn lẻ của số mũ các số nguyên tố 
  15. // 	 (bit thứ i là 0: số nguyên tố thứ i (prime[i]) có số mũ là chẵn
  16. //	  bit thứ i là 1: số nguyên tố thứ i (prime[i]) có số mũ là lẻ)
  17. // => dp[i][mask] = Số tập con khác nhau khi xét i phần tử đầu tiên, 
  18. //                  với mask biểu diễn tính chẵn lẻ của số mũ các số nguyên tố trong phân tích thừa số của tích các phần tử có trong tập con
  19. // => Độ phức tạp: O(n * 2^19)
  20. // Tối ưu: Tận dụng max({a(i)}) <= 70 => DP theo giá trị thay vì theo chỉ số
  21. // => dp[x][mask] = Số tập con khác nhau khi xét các giá trị từ 1 đến x,
  22. //                  với mask biểu diễn ... 
  23. // => Công thức dp lúc này yêu cầu kiến thức về tổ hợp cũng như tính chất của phép xor
  24. // - Tính chất phép xor:
  25. //   x ^ 0 = x 
  26. //   x ^ x = 0
  27. // - Tổ hợp: Số cách chọn chẵn/lẻ phần tử từ tập có n phần tử = 2^(n - 1) 
  28. // => Độ phức tạp: O(MAX_A * 2^19)
  29. const int N = 1e5 + 5; 
  30. const int MAX_A = 70; 
  31. const int MOD = 1e9 + 7;   
  32.  
  33. void add(int& a, int b) {
  34. 	a += b; 
  35. 	if (a >= MOD) a -= MOD; 
  36. 	if (a < 0) a += MOD; 
  37. }
  38.  
  39. int prime[19] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}; 
  40. int n;  
  41. int a[N];
  42. int cnt[MAX_A + 5]; // cnt[x] = Số lần xuất hiện của x trong mảng a
  43.  
  44. int pow2[N]; // pow2[i] = 2^i % MOD
  45. int prime_mask[MAX_A + 5]; // prime_mask[x] = mask biểu diễn tính chẵn lẻ của số mũ các số nguyên tố trong phân tích thừa số của x
  46. int dp[MAX_A + 5][1 << 19]; // dp[x][mask]  
  47.  
  48. int main() {
  49. 	ios::sync_with_stdio(false); 
  50. 	cin.tie(nullptr); 	
  51. 	cin >> n; 
  52. 	for (int i = 1; i <= n; i++) {
  53. 		cin >> a[i];
  54. 		cnt[a[i]]++; 
  55. 	} 
  56.  
  57. 	pow2[0] = 1; 
  58. 	for (int i = 1; i <= n; i++) pow2[i] = pow2[i - 1] * 2 % MOD; 
  59.  
  60. 	for (int x = 1; x <= MAX_A; x++) {
  61. 		int tmp = x;  
  62. 		for (int i = 0; i < 19; i++) {
  63. 			int e = 0;   
  64. 			while (tmp % prime[i] == 0) {
  65. 				tmp /= prime[i]; 
  66. 				e += 1; 
  67. 			}
  68. 			if (e & 1) prime_mask[x] |= (1 << i); 
  69. 		}
  70. 	}
  71.  
  72. 	dp[0][0] = 1; 
  73. 	for (int x = 1; x <= MAX_A; x++) {
  74. 		for (int prev_mask = 0; prev_mask < (1 << 19); prev_mask++) {
  75. 			if (cnt[x] == 0) {
  76. 				add(dp[x][prev_mask], dp[x - 1][prev_mask]); 
  77. 			}
  78. 			else {
  79. 				// Thêm vào tập hợp trước đó chẵn phần tử có giá trị là x
  80. 				add(dp[x][prev_mask], 1ll * dp[x - 1][prev_mask] * pow2[cnt[x] - 1] % MOD);
  81. 				// Thêm vào tập hợp trước đó lẻ phần tử có giá trị là x
  82. 				add(dp[x][prev_mask ^ prime_mask[x]], 1ll * dp[x - 1][prev_mask] * pow2[cnt[x] - 1] % MOD); 
  83. 			}
  84. 		}
  85. 	}
  86.  
  87. 	int ans = dp[MAX_A][0]; 
  88. 	add(ans, -1); // Trừ đi trường hợp tập rỗng 
  89.  
  90. 	cout << ans << '\n'; 
  91. }
Success #stdin #stdout 0.18s 149032KB
comments (?)
stdin
copy 
4
1 1 1 1
stdout
copy 
15
https://ideone.com/TFA2rB
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!