fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. // #define int long long
  4. typedef long long ll;
  5. typedef pair<int, int> ii;
  6. typedef pair<int, ii> iii;
  7.  
  8. template<class T>
  9.     bool minimize(T &a, const T &b) {
  10.         if (a > b) return a = b, true;
  11.         return false;
  12.     }
  13.  
  14. template<class T>
  15.     bool maximize(T &a, const T &b) {
  16.         if (a < b) return a = b, true;
  17.         return false;
  18.     }
  19.  
  20. #define FOR(i, a, b) for (int i = a; i <= (int)b; i++)
  21. #define FORD(i, a, b) for (int i = a; i >= (int)b; i--)
  22. #define MASK(i) (1LL << (i))
  23. #define BIT(S, i) (((S) >> (i)) & 1)
  24. #define mp make_pair
  25. #define pb push_back
  26. #define fi first
  27. #define se second
  28. #define all(x) x.begin(), x.end()
  29. const int N = 5e5 + 5;
  30. const int mod = 1e9 + 7;
  31. const int base = 311;
  32.  
  33. int n, m;
  34. char a[255][255];
  35. int sum[255][255][28];
  36. bool okRow[255];
  37. int hsh[255], pw[255];
  38. int pre_hash[255], suf_hash[255], farLeft[255], farRight[255];
  39.  
  40. void init(void) {
  41. 	cin >> n >> m;
  42. 	FOR(i, 1, n) FOR(j, 1, m) cin >> a[i][j];
  43. }
  44.  
  45. bool PalinRow(int id, int l, int r) {
  46. 	int cntOdd = 0, cntEven = 0;
  47. 	FOR(c, 0, 25) {
  48. 		int cnt = sum[id][r][c] - sum[id][l - 1][c];
  49. 		if (cnt & 1) cntOdd++;
  50. 		else cntEven++;
  51. 	}
  52. 	if ((r - l + 1) % 2 == 0) return cntOdd == 0;
  53. 	return cntOdd <= 1;
  54. }
  55.  
  56. int getHashPre(int l, int r) {
  57. 	return (pre_hash[r] - 1LL * pre_hash[l - 1] * pw[r - l + 1] % mod + 1LL * mod * mod) % mod;
  58. }
  59.  
  60. int getHashSuf(int l, int r) {
  61. 	return (suf_hash[l] - 1LL * suf_hash[r + 1] * pw[r - l + 1] % mod + 1LL * mod * mod) % mod;
  62. }
  63.  
  64. void process(void) {
  65. 	FOR(c, 0, 25) FOR(i, 1, n) FOR(j, 1, m) sum[i][j][c] = sum[i][j - 1][c] + ((a[i][j] - 'a') == c);
  66. 	pw[0] = 1;
  67. 	FOR(i, 1, n) pw[i] = 1LL * pw[i - 1] * base % mod;
  68. 	int ans = 0;
  69. 	FOR(col1, 1, m) FOR(col2, col1, m) {
  70. 		FOR(row, 1, n) {
  71. 			okRow[row] = PalinRow(row, col1, col2);
  72. 			if(okRow[row] == 0) continue;
  73. 			int _s = 0;
  74. 			FOR(c, 0, 25) {
  75. 				int tam = (sum[row][col2][c] - sum[row][col1 - 1][c]);
  76. 				_s = 1LL * _s * base % mod + tam;
  77. 				_s %= mod;
  78. 			}
  79. 			hsh[row] = _s;
  80. 		}		
  81. 		FOR(row, 1, n) {
  82. 			farLeft[row] = okRow[row] ? farLeft[row - 1] : row;
  83. 			pre_hash[row] = 1LL * pre_hash[row - 1] * base % mod + hsh[row] % mod; 
  84. 		}
  85. 		farRight[n + 1] = n + 1;
  86. 		FORD(row, n, 1) {
  87. 			farRight[row] = okRow[row] ? farRight[row + 1] : row;
  88. 			suf_hash[row] = 1LL * suf_hash[row + 1] * base % mod + hsh[row] % mod;
  89. 		}	
  90. 		if (1) {
  91. 			FOR(i, 1, n) {
  92. 				int l = 1, r = min(i - farLeft[i], farRight[i] - i);
  93. 				int res = 0;
  94. 				while (l <= r) {
  95. 					int mid = (l + r) >> 1;
  96. 					int hsh_left = getHashPre(i - mid + 1, i);
  97. 					int hsh_right = getHashSuf(i, i + mid - 1);
  98. 					if(hsh_left == hsh_right) {
  99. 						res = mid, l = mid + 1;
  100. 					} else r = mid - 1;
  101. 				}
  102. 				ans+= res;
  103. 			}
  104. 		}
  105. 		if (1) {
  106. 			FOR(i, 1, n) {
  107. 				int l = 1, r = min(i - farLeft[i], farRight[i + 1] - (i + 1));
  108. 				int res = 0;
  109. 				while (l <= r) {
  110. 					int mid = (l + r) >> 1;
  111. 					int hsh_left = getHashPre(i - mid + 1, i);
  112. 					int hsh_right = getHashSuf(i + 1, i + 1 + mid - 1);
  113. 					if(hsh_left == hsh_right) {
  114. 						res = mid, l = mid + 1;
  115. 					} else r = mid - 1;
  116. 				}
  117. 				ans+= res;
  118. 			}
  119. 		}
  120. 	}	
  121. 	cout << ans;
  122. }
  123.  
  124. signed main(void) {
  125.     ios_base::sync_with_stdio(false);
  126.     cin.tie(nullptr);
  127.     #define taskname "kieuoanh"
  128.     if (fopen(taskname".inp", "r")) {
  129.         freopen(taskname".inp", "r", stdin);
  130.         freopen(taskname".out", "w", stdout);
  131.     }
  132.     init();
  133.     process();
  134.     return 0;
  135. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bE1Dvz
language:
C++14 (gcc 8.3)
created:
3 days 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!