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 MOD = 1e9 + 7;  
  12. const int N = 1e5 + 5; 
  13. const int K = 1e5 + 5; 
  14.  
  15. void add(int& a, int b) {
  16. 	a += b; 
  17. 	if (a >= MOD) a -= MOD; 
  18. 	if (a < 0) a += MOD; 
  19. }
  20.  
  21. struct Trie {	
  22. 	struct Node {
  23. 		int nxt[2]; 
  24. 		int sum = 0; // tổng val
  25.  
  26. 		Node() {
  27. 			memset(nxt, -1, sizeof nxt); 
  28. 		}
  29. 	}; 
  30.  
  31. 	vector<Node> trie;  
  32.  
  33. 	Trie() {
  34. 		trie = vector<Node>(1); 
  35. 	}
  36.  
  37. 	// Số nguyên x mang theo giá trị val
  38. 	void addNumber(int x, int val) {
  39. 		int v = 0;  
  40. 		for (int i = 29; i >= 0; i--) {
  41. 			int c = (x >> i) & 1; 
  42. 			if (trie[v].nxt[c] == -1) {
  43. 				trie[v].nxt[c] = trie.size(); 
  44. 				trie.push_back(Node()); 
  45. 			}
  46. 			v = trie[v].nxt[c];
  47. 			add(trie[v].sum, val); 
  48. 		}
  49. 	}
  50.  
  51. 	// Tính tổng val của các số y có trong cây trie sao cho y ^ x <= mx
  52. 	int getSum(int x, int mx) {
  53. 		int v = 0, ans = 0; 
  54. 		for (int i = 29; i >= 0; i--) {
  55. 			int c = (x >> i) & 1, max_c = (mx >> i) & 1;  
  56. 			int nxt_v0 = trie[v].nxt[c], nxt_v1 = trie[v].nxt[c ^ 1]; 
  57. 			if (max_c == 0) {
  58. 				v = nxt_v0;   
  59. 			}
  60. 			else {
  61. 				if (nxt_v0 != -1) add(ans, trie[nxt_v0].sum); 
  62. 				v = nxt_v1; 
  63. 			}
  64. 			if (v == -1) break; 
  65. 		}
  66. 		if (v != -1) add(ans, trie[v].sum); 
  67.  
  68. 		return ans; 
  69. 	}
  70. }; 
  71.  
  72. Trie trie[K];
  73.  
  74. int n, k;  
  75. int a[N], pref_xor[N]; 
  76. int l[K], r[K]; 
  77. vector<int> dp[N]; // dp[i][j] = Số cách chia đoạn [1, i] thành j đoạn con liên tiếp thoả mãn điều kiện
  78.  
  79. int main() {
  80. 	ios::sync_with_stdio(false); 
  81. 	cin.tie(nullptr); 	
  82. 	cin >> n >> k; 
  83. 	for (int i = 1; i <= n; i++) cin >> a[i]; 
  84. 	for (int i = 1; i <= k; i++) cin >> l[i] >> r[i];
  85.  
  86. 	for (int i = 1; i <= n; i++) {
  87. 		pref_xor[i] = pref_xor[i - 1] ^ a[i]; 
  88. 	}
  89.  
  90. 	for (int i = 0; i <= n; i++) {
  91. 		dp[i] = vector<int>(k + 1, 0); 
  92. 	}
  93. 	dp[0][0] = 1;  
  94.  
  95. 	// for (int i = 1; i <= n; i++) {
  96. 	// 	for (int j = 1; j <= k; j++) {
  97. 	// 		for (int prev_i = 0; prev_i < i; prev_i++) {
  98. 	// 			int sum_xor = pref_xor[i] ^ pref_xor[prev_i];  
  99. 	// 			if (l[j] <= sum_xor && sum_xor <= r[j]) {
  100. 	// 				add(dp[i][j], dp[prev_i][j - 1]); 
  101. 	// 			}
  102. 	// 		}
  103. 	// 	}
  104. 	// }	
  105.  
  106. 	trie[0].addNumber(pref_xor[0], dp[0][0]); 
  107.  
  108. 	for (int i = 1; i <= n; i++) {
  109. 		for (int j = 1; j <= k; j++) {
  110. 			int sum_dp = trie[j - 1].getSum(pref_xor[i], r[j]); 
  111. 			add(sum_dp, -trie[j - 1].getSum(pref_xor[i], l[j] - 1)); 
  112. 			add(dp[i][j], sum_dp); 
  113. 		}
  114. 		for (int j = 1; j <= k; j++) {
  115. 			trie[j].addNumber(pref_xor[i], dp[i][j]); 
  116. 		}
  117. 	}
  118.  
  119. 	cout << dp[n][k] << '\n'; 
  120. }
Success #stdin #stdout 0.02s 12932KB
comments (?)
stdin
copy 
4 2
1 2 3 4
1 4
2 10
stdout
copy 
2
https://ideone.com/wlKPs9
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!