Advertisement
Guest User

Untitled

a guest
Nov 2nd, 2019
394
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.35 KB | None | 0 0
  1. #pragma GCC optimize("Ofast")
  2. #include <bits/stdc++.h>
  3. #define isz(x) (int)(x).size()
  4. #define all(x) (x).begin(),(x).end()
  5. const int NMAX = 1000010;
  6. typedef unsigned long long ull;
  7. const ull seed = (ull)(std::make_unique<char>().get()) ^
  8.     (ull)(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  9. const ull mod = (ull(1) << 61) - 1;
  10. std::mt19937 gen(seed);
  11. const ull base = std::uniform_int_distribution<ull>(mod/10,mod-10)(gen) | 1;
  12. ull Pow[NMAX];
  13. ull mul(ull a, ull b) {
  14.     ull a0 = (uint32_t)a, b0 = (uint32_t)b;
  15.     ull a1 = a >> 32, b1 = b >> 32;
  16.     ull high = ((a1 * b1 << 3) & mod) + ((a1 * b1) >> 58);
  17.     ull mid = ((a1 * b0 + b1 * a0) >> 29) + (((a1 * b0 + b1 * a0) << 32) & mod);
  18.     ull ret = high + mid + ((a0 * b0) >> 61) + ((a0 * b0) & mod) + 1;
  19.     ret = (ret >> 61) + (ret & mod);
  20.     ret = (ret >> 61) + (ret & mod);
  21.     return ret - 1;
  22. }
  23. ull add(ull a, ull b) {
  24.     return (a += b) >= mod ? a -= mod : a;
  25. }
  26. ull sub(ull a, ull b) {
  27.     return (a -= b) >= mod ? a += mod : a;
  28. }
  29. struct Hash {
  30.     std::array<ull, NMAX> hash;
  31.     Hash(const std::string& s) {
  32.         hash[0] = 0;
  33.         for (int i = 0; i < isz(s); i++) {
  34.             hash[i+1] = add(mul(hash[i], base), s[i]);
  35.         }
  36.     }
  37.     ull operator()(int begin, int length) const {
  38.         return sub(hash[begin+length], mul(Pow[length], hash[begin]));
  39.     }
  40. };
  41. int main() {
  42.     Pow[0] = 1;
  43.     for (int i = 1; i < NMAX; i++) { Pow[i] = mul(Pow[i-1], base); }
  44.     std::ios_base::sync_with_stdio(false); std::cin.tie(0);
  45.     for (std::string s; std::cin >> s; ) {
  46.         auto t = s; std::reverse(all(t));
  47.         Hash ht(t), hs(s);
  48.         ull answ = 0;
  49.         for (int i = 0; i < isz(s); i++) {
  50.             int low = 1, high = std::min(i+1, isz(s)-i)+1;
  51.             while (high - low > 1) {
  52.                 int mid = (low + high) / 2;
  53.                 if (hs(i, mid) == ht(isz(s)-i-1, mid)) { low = mid; }
  54.                 else { high = mid; }
  55.             }
  56.             answ += low;
  57.             low = 0; high = std::min(i+1, isz(s)-i-1)+1;
  58.             while (high - low > 1) {
  59.                 int mid = (low + high) / 2;
  60.                 if (hs(i+1, mid) == ht(isz(s)-i-1, mid)) { low = mid; }
  61.                 else { high = mid; }
  62.             }
  63.             answ += low;
  64.         }
  65.         std::cout << answ << std::endl;
  66.     }
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement