Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- #include <bits/stdc++.h>
- #define isz(x) (int)(x).size()
- #define all(x) (x).begin(),(x).end()
- const int NMAX = 1000010;
- typedef unsigned long long ull;
- const ull seed = (ull)(std::make_unique<char>().get()) ^
- (ull)(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- const ull mod = (ull(1) << 61) - 1;
- std::mt19937 gen(seed);
- const ull base = std::uniform_int_distribution<ull>(mod/10,mod-10)(gen) | 1;
- ull Pow[NMAX];
- ull mul(ull a, ull b) {
- ull a0 = (uint32_t)a, b0 = (uint32_t)b;
- ull a1 = a >> 32, b1 = b >> 32;
- ull high = ((a1 * b1 << 3) & mod) + ((a1 * b1) >> 58);
- ull mid = ((a1 * b0 + b1 * a0) >> 29) + (((a1 * b0 + b1 * a0) << 32) & mod);
- ull ret = high + mid + ((a0 * b0) >> 61) + ((a0 * b0) & mod) + 1;
- ret = (ret >> 61) + (ret & mod);
- ret = (ret >> 61) + (ret & mod);
- return ret - 1;
- }
- ull add(ull a, ull b) {
- return (a += b) >= mod ? a -= mod : a;
- }
- ull sub(ull a, ull b) {
- return (a -= b) >= mod ? a += mod : a;
- }
- struct Hash {
- std::array<ull, NMAX> hash;
- Hash(const std::string& s) {
- hash[0] = 0;
- for (int i = 0; i < isz(s); i++) {
- hash[i+1] = add(mul(hash[i], base), s[i]);
- }
- }
- ull operator()(int begin, int length) const {
- return sub(hash[begin+length], mul(Pow[length], hash[begin]));
- }
- };
- int main() {
- Pow[0] = 1;
- for (int i = 1; i < NMAX; i++) { Pow[i] = mul(Pow[i-1], base); }
- std::ios_base::sync_with_stdio(false); std::cin.tie(0);
- for (std::string s; std::cin >> s; ) {
- auto t = s; std::reverse(all(t));
- Hash ht(t), hs(s);
- ull answ = 0;
- for (int i = 0; i < isz(s); i++) {
- int low = 1, high = std::min(i+1, isz(s)-i)+1;
- while (high - low > 1) {
- int mid = (low + high) / 2;
- if (hs(i, mid) == ht(isz(s)-i-1, mid)) { low = mid; }
- else { high = mid; }
- }
- answ += low;
- low = 0; high = std::min(i+1, isz(s)-i-1)+1;
- while (high - low > 1) {
- int mid = (low + high) / 2;
- if (hs(i+1, mid) == ht(isz(s)-i-1, mid)) { low = mid; }
- else { high = mid; }
- }
- answ += low;
- }
- std::cout << answ << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement