Submission #982690

#TimeUsernameProblemLanguageResultExecution timeMemory
982690AlebnPalindromic Partitions (CEOI17_palindromic)C++14
0 / 100
18 ms16108 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int n, M = 1e9+7, P = 31, N = 1e6 + 1; string s; vector<int> p, inv, haah; int mod(int i) { return (i + M) % M; } int fast(int i, int j) { //cout << i << " " << j << "\n"; if(j == 0) return 1; int a = fast(i, j / 2); return mod(mod(a * a) * (j % 2 == 0 ? 1 : i)); } signed main() { int t; cin >> t; // p = vector<int>(N), inv = vector<int>(N); p[0] = 1; for(int i = 1; i < N; i++) p[i] = mod(p[i - 1] * P); inv[N - 1] = fast(p[N - 1], M - 2); for(int i = N - 2; i > -1; i--) inv[i] = mod(inv[i + 1] * P); // while(t--) { cin >> s; n = s.size(), haah = vector<int>(n); for(int i = 0; i < n; i++) { haah[i] = mod((s[i] - 'a') * p[i]); if(i != 0) haah[i] = mod(haah[i - 1] + haah[i]); //cout << haah[i] << " "; } // int res = 0, last = 0, a, b; for(int i = 0; i < n / 2; i++) { a = mod(haah[i] - (last == 0 ? 0 : haah[last - 1])); a = mod(a * inv[last]); b = mod(haah[n - last - 1] - (n - i - 2 < 0 ? 0 : haah[n - i - 2])); b = mod(b * inv[n - i - 1]); // /*a = 0; for(int j = last; j < i + 1; j++) { a = mod(a + mod((s[j] - 'a') * p[j - last])); } // b = 0; for(int j = n - i - 1; j < n - last; j++) { b = mod(b + mod((s[j] - 'a') * p[j - (n - i - 1)])); }*/ // //cout << last << " " << i << " " << a << " 1\n"; //cout << n - i - 1 << " " << n - last - 1 << " " << b << " 2\n"; if(a == b) { res += 2; last = i + 1; if(i == n / 2 - 1 && n % 2 == 1) res++; } else if(i == n / 2 - 1) res++; } // cout << res << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...