fork download 
  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 p = 311; 
  12. const int MOD = 1e9 + 9277; 
  13. const int N = 5e6 + 5; 
  14.  
  15. int n; 
  16. string s; 
  17. int p_pow[N], h[N]; 
  18. int inv_p_pow[N], rev_h[N]; 
  19.  
  20. int binpow(int a, int b) {
  21. 	int ans = 1; 
  22. 	for (; b > 0; b >>= 1) {
  23. 		if (b & 1) ans = 1ll * ans * a % MOD;  
  24. 		a = 1ll * a * a % MOD; 
  25. 	}
  26. 	return ans;
  27. }
  28.  
  29. void precompute() {
  30. 	p_pow[0] = 1; 
  31. 	for (int i = 1; i <= n; i++) {
  32. 		p_pow[i] = 1ll * p_pow[i - 1] * p % MOD;  
  33. 	}
  34.  
  35. 	inv_p_pow[n] = binpow(p_pow[n], MOD - 2); 
  36. 	for (int i = n - 1; i >= 0; i--) {
  37. 		inv_p_pow[i] = 1ll * inv_p_pow[i + 1] * p % MOD; 
  38. 	}
  39.  
  40. 	h[0] = rev_h[0] = 0;  
  41. 	for (int i = 1; i <= n; i++) {
  42. 		h[i] = (1ll * h[i - 1] * p + s[i]) % MOD; 
  43. 		rev_h[i] = (rev_h[i - 1] + 1ll * s[i] * p_pow[i - 1] % MOD) % MOD; 
  44. 	}
  45. }
  46.  
  47. int getHash(int l, int r) {
  48. 	return (h[r] - 1ll * h[l - 1] * p_pow[r - l + 1] % MOD + MOD) % MOD; 
  49. }
  50.  
  51. int getRevHash(int l, int r) {
  52. 	return 1ll * (rev_h[r] - rev_h[l - 1] + MOD) % MOD * inv_p_pow[l - 1] % MOD; 
  53. }
  54.  
  55. bool isPalin(int l, int r) {
  56. 	return (getHash(l, r) == getRevHash(l, r)); 
  57. }
  58.  
  59. int memo[N];  
  60.  
  61. // Bậc đối xứng của xâu s[1..i]
  62. int deg(int i) {
  63. 	if (i == 0 || !isPalin(1, i)) return 0;  
  64. 	int& ans = memo[i];  
  65. 	if (ans != -1) return ans;  
  66. 	return ans = 1 + deg(i / 2); 
  67. }
  68.  
  69. int main() {
  70. 	ios::sync_with_stdio(false); 
  71. 	cin.tie(nullptr); 	
  72. 	cin >> s; 
  73. 	n = s.size(); 
  74. 	s = ' ' + s;  
  75.  
  76. 	precompute();  
  77.  
  78. 	memset(memo, -1, sizeof memo);  
  79.  
  80. 	ll ans = 0;  
  81. 	for (int i = 1; i <= n; i++) ans += deg(i);  
  82.  
  83. 	cout << ans << '\n'; 
  84. }
Success #stdin #stdout 0.01s 29836KB
comments (?)
stdin 
a2A
stdout 
1
https://ideone.com/TpVKAi
language:
C++14 (gcc 8.3)
created:
338 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!