fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int MOD = 1e9 + 7;  
  11.  
  12. int n;  
  13. string s;
  14.  
  15. int what_subtask() {
  16. 	if (n <= 20) return 1;  	 
  17. 	if (n <= 1000) return 2; 
  18. 	return 3; 
  19. }
  20.  
  21. void add(int& a, int b) {
  22. 	a = (a + b) % MOD;  
  23. 	if (a < 0) a += MOD;  
  24. }
  25.  
  26. namespace sub1 {
  27. 	int ans;    
  28.  
  29. 	bool ok(const string& t) {
  30. 		int sz = t.size(); 
  31. 		for (int i = 0; i + 1 < sz; i++) {
  32. 			if (i % 2 == 0) {
  33. 				if (t[i] >= t[i + 1]) return false; 
  34. 			}
  35. 			else {
  36. 				if (t[i] <= t[i + 1]) return false; 
  37. 			}
  38. 		}
  39. 		return true;  
  40. 	}
  41.  
  42. 	void backtrack(int i, string& t) {
  43. 		if (i == n + 1) {
  44. 			ans += ok(t); 
  45. 			return; 
  46. 		}
  47.  
  48. 		backtrack(i + 1, t);  
  49.  
  50. 		t += s[i];  
  51. 		backtrack(i + 1, t);  
  52. 		t.pop_back();  
  53. 	}
  54.  
  55. 	void solve() {
  56. 		string t = ""; 
  57. 		ans = 0;   
  58.  
  59. 		backtrack(1, t); 
  60.  
  61. 		cout << ans - 1 << '\n'; 
  62. 	}
  63. }
  64.  
  65. namespace sub2 {
  66. 	const int N = 1e3 + 5;  
  67.  
  68. 	int dp[N][2]; // 0 chẵn, 1 lẻ 
  69.  
  70. 	void solve() {
  71. 		for (int i = 1; i <= n; i++) {
  72. 			dp[i][1] = 1; // xâu chỉ chứa 1 kí tự s[i]  
  73.  
  74. 			for (int parity = 0; parity <= 1; parity++) {
  75. 				for (int j = 1; j < i; j++) {
  76. 					if (parity == 0 && s[j] < s[i]) {
  77. 						add(dp[i][parity], dp[j][parity ^ 1]); 
  78. 					}	
  79.  
  80. 					if (parity == 1 && s[j] > s[i]) {
  81. 						add(dp[i][parity], dp[j][parity ^ 1]); 
  82. 					}
  83. 				}
  84. 			}
  85. 		}
  86.  
  87. 		int ans = 0;   
  88. 		for (int i = 1; i <= n; i++) {
  89. 			for (int parity = 0; parity <= 1; parity++) {
  90. 				add(ans, dp[i][parity]); 
  91. 			}
  92. 		}
  93.  
  94. 		cout << ans << '\n'; 
  95. 	}
  96. }
  97.  
  98. namespace sub3 {
  99. 	const int N = 1e6 + 5;  
  100.  
  101. 	int dp[N][2]; // 0 chẵn, 1 lẻ 
  102. 	int sum[2][26];  
  103.  
  104. 	int getSum(int parity, int l, int r) {
  105. 		if (l > r) return 0;  
  106. 		return sum[parity][r] - ((l <= 0) ? 0 : sum[parity][l - 1]); 
  107. 	}
  108.  
  109. 	void solve() {
  110. 		for (int i = 1; i <= n; i++) {
  111. 			dp[i][1] = 1; // xâu chỉ chứa 1 kí tự s[i]  
  112.  
  113. 			for (int parity = 0; parity <= 1; parity++) {
  114. 				if (parity == 0) {
  115. 					add(dp[i][0], getSum(1, 0, (s[i] - 'A') - 1)); 
  116. 				}	
  117.  
  118. 				if (parity == 1) {
  119. 					add(dp[i][1], getSum(0, (s[i] - 'A') + 1, 25)); 
  120. 				}
  121. 			}
  122.  
  123. 			for (int parity = 0; parity <= 1; parity++) {
  124. 				for (int c = (s[i] - 'A'); c <= 25; c++) add(sum[parity][c], dp[i][parity]); 
  125. 			}
  126. 		}	
  127.  
  128. 		int ans = 0;   
  129. 		for (int i = 1; i <= n; i++) {
  130. 			for (int parity = 0; parity <= 1; parity++) {
  131. 				add(ans, dp[i][parity]); 
  132. 			}
  133. 		}
  134.  
  135. 		cout << ans << '\n'; 
  136. 	}
  137. }
  138.  
  139. int main() {
  140. 	ios::sync_with_stdio(0); cin.tie(0);  	
  141. 	cin >> s;  
  142. 	n = s.size();  
  143. 	s = ' ' + s;  
  144.  
  145. 	int subtask = what_subtask(); 
  146.  
  147. 	if (subtask == 1) sub1::solve(); 
  148. 	if (subtask == 2) sub2::solve(); 
  149. 	if (subtask == 3) sub3::solve(); 
  150. }
  151.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
ACB
stdout
copy 
6
https://ideone.com/b95DUi
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!