fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28.  
  29.  
  30. string a;
  31.  
  32. //* Pivot 1st palindrome substring
  33.  
  34. int consistency1(int n){
  35.  
  36. 	vector<vector<bool>> dp(n, vector<bool>(n, false));
  37. 	vector<vector<int>> dpCt(n, vector<int>(n, 0));
  38.  
  39. 	for(int gap=0; gap<n; gap++){
  40. 		for(int i=0, j=gap; j<n; i++, j++){
  41. 			if(gap == 0){
  42. 				dp[i][j] = true;
  43. 				dpCt[i][j] = 1;
  44. 			}
  45. 			else if(gap == 1){
  46. 				if(a[i] == a[j]){
  47. 					dp[i][j] = true;
  48. 					dpCt[i][j] = 3;
  49. 				}
  50. 				else{
  51. 					dpCt[i][j] = 2;
  52. 				}
  53. 			}
  54. 			else{
  55. 				dpCt[i][j] = dpCt[i][j-1] + dpCt[i+1][j] - dpCt[i+1][j-1];
  56. 				if(a[i] == a[j] && dp[i+1][j-1]){
  57. 					dp[i][j] = true;
  58. 					dpCt[i][j]++;
  59. 				}
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	int ans = 0;
  65. 	for(int i=0; i<=n-3; i++){
  66. 		int x = 0;
  67.  
  68. 		int j = i;
  69. 		while(j>=0){
  70. 			if(dp[j][i]) x++;
  71. 			j--;
  72. 		}
  73.  
  74. 		int y = 0;
  75. 		for(int j=i+1; j<=n-2; j++){
  76. 			int p = 0;
  77.  
  78. 			int k = j;
  79. 			while(k>i){
  80. 				if(dp[k][j]) p++;
  81. 				k--;
  82. 			}
  83. 			int q = dpCt[j+1][n-1];
  84.  
  85. 			y += p*q;
  86. 		}
  87.  
  88. 		ans += x*y;
  89. 	}
  90.  
  91.     return ans;
  92. }
  93.  
  94.  
  95.  
  96.  
  97.  
  98.  
  99.  
  100. //* Pivot 1st palindrome substring
  101.  
  102. int consistency2(int n){
  103.  
  104. 	vector<vector<bool>> dp(n, vector<bool>(n, false));
  105. 	vector<vector<int>> dpCt(n, vector<int>(n, 0));
  106.  
  107. 	for(int gap=0; gap<n; gap++){
  108. 		for(int i=0, j=gap; j<n; i++, j++){
  109. 			if(gap == 0){
  110. 				dp[i][j] = true;
  111. 				dpCt[i][j] = 1;
  112. 			}
  113. 			else if(gap == 1){
  114. 				if(a[i] == a[j]){
  115. 					dp[i][j] = true;
  116. 					dpCt[i][j] = 3;
  117. 				}
  118. 				else{
  119. 					dpCt[i][j] = 2;
  120. 				}
  121. 			}
  122. 			else{
  123. 				dpCt[i][j] = dpCt[i][j-1] + dpCt[i+1][j] - dpCt[i+1][j-1];
  124. 				if(a[i] == a[j] && dp[i+1][j-1]){
  125. 					dp[i][j] = true;
  126. 					dpCt[i][j]++;
  127. 				}
  128. 			}
  129. 		}
  130. 	}
  131.  
  132.  
  133. 	vector<int> endsAt(n, 0);
  134. 	for(int j = 0; j < n; j++){
  135. 		for(int i = 0; i <= j; i++){
  136. 			if(dp[i][j]) endsAt[j]++;
  137. 		}
  138. 	}
  139.  
  140. 	vector<int> pairsStartsAt(n, 0);
  141. 	for(int i = 0; i <= n - 2; i++){
  142. 		for(int j = i; j <= n - 2; j++){
  143. 			if(dp[i][j]){
  144. 				int x = 1;
  145. 				int y = dpCt[j+1][n-1];
  146. 				pairsStartsAt[i] += x*y;
  147. 			}
  148. 		}
  149. 	}
  150.  
  151. 	vector<int> suffixPairs(n + 1, 0);
  152. 	for(int i = n - 2; i >= 1; i--){
  153. 		suffixPairs[i] = suffixPairs[i+1] + pairsStartsAt[i];
  154. 	}
  155.  
  156. 	int ans = 0;
  157. 	for(int j = 0; j <= n - 3; j++){
  158. 		ans += endsAt[j] * suffixPairs[j+1];
  159. 	}
  160.  
  161. 	return ans;
  162. }
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170. //* Pivot middle palindrome substring
  171.  
  172. int consistency3(int n){
  173.  
  174. 	vector<vector<bool>> dp(n, vector<bool>(n, false));
  175. 	vector<vector<int>> dpCt(n, vector<int>(n, 0));
  176. 	vector<int> dp2(n, 0);
  177.  
  178. 	for(int gap=0; gap<n; gap++){
  179. 		for(int i=0, j=gap; j<n; i++, j++){
  180. 			if(gap == 0){
  181. 				dp[i][j] = true;
  182. 				dpCt[i][j] = 1;
  183. 				dp2[j] += 1;
  184. 			}
  185. 			else if(gap == 1){
  186. 				if(a[i] == a[j]){
  187. 					dp[i][j] = true;
  188. 					dpCt[i][j] = 3;
  189. 					dp2[j] += 1;
  190. 				}
  191. 				else{
  192. 					dpCt[i][j] = 2;
  193. 				}
  194. 			}
  195. 			else{
  196. 				dpCt[i][j] = dpCt[i][j-1] + dpCt[i+1][j] - dpCt[i+1][j-1];
  197. 				if(a[i] == a[j] && dp[i+1][j-1]){
  198. 					dp[i][j] = true;
  199. 					dpCt[i][j]++;
  200. 					dp2[j]++;
  201. 				}
  202. 			}
  203. 		}
  204. 	}
  205.  
  206. 	int ans = 0;
  207. 	for(int j=0; j<=n-2; j++){
  208. 		int z = dpCt[j+1][n-1];
  209.  
  210. 		int i = j;
  211. 		while(i>=1){
  212. 			if(dp[i][j]){
  213. 				int x = dpCt[0][i-1];
  214.  
  215. 				ans += x*1*z;
  216. 			}
  217.  
  218. 			i--;
  219. 		}
  220. 	}
  221.  
  222.     return ans;
  223. }
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235. int practice(int n){
  236.  
  237.  
  238.     return 0;
  239. }
  240.  
  241.  
  242.  
  243.  
  244.  
  245. void solve() {
  246.  
  247.     cin >> a;
  248.     int n = a.size();
  249.     cout << consistency1(n) << " " << consistency2(n) << " " << consistency3(n) << endl;
  250.  
  251.  
  252. }
  253.  
  254.  
  255.  
  256.  
  257.  
  258. int32_t main() {
  259.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  260.  
  261.     int t = 1;
  262.     // cin >> t;
  263.     while (t--) {
  264.         solve();
  265.     }
  266.  
  267.     return 0;
  268. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
pcbcqqcbcpsfdf
stdout
copy 
760 760 760
https://ideone.com/Ma0n4r
language:
C++14 (gcc 8.3)
created:
1 day 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!