結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー しらっ亭
提出日時 2016-12-12 05:46:30
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 171 ms / 2,000 ms
コード長 2,938 bytes
コンパイル時間 2,007 ms
コンパイル使用メモリ 186,276 KB
実行使用メモリ 15,680 KB
最終ジャッジ日時 2024-11-30 07:12:18
合計ジャッジ時間 4,428 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

struct Manacher {
  vector<int> rads;

  // O(|s|)
  Manacher(const string &s) : rads(s.size() * 2 - 1){
    int size = (int) rads.size();
    int i = 0, j = 0;
    while (i < size) {
      while (i - j >= 0 && i + j < size && get(s, i - j) == get(s, i + j)) {
        ++j;
      }
      rads[i] = j;
      int k = 1;
      while (i - k >= 0 && i + k < size && k + rads[i - k] < j) {
        rads[i + k] = rads[i - k], ++k;
      }
      i += k;
      j -= k;
    }
  }

  // s[l, r] is palindrome?
  // O(1)
  bool is_palindrome(int l, int r) {
    assert(l >= 0);
    assert(r >= l);
    assert(r * 2 <= (int) rads.size());

    return rads[l + r] >= r - l + 1;
  }

  private:
  static char get(const string &s, int i) {
    if (i & 1) return '^';
    else return s[i >> 1];
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  string s;
  cin >> s;

  int n = s.size();

  assert(n >= 4 && n <= 500000);
  for (char c : s) assert(c >= 'a' && c <= 'z');

  Manacher mana(s);

  vector<int> pl(n);
  vector<int> gpl(n + 1);
  vector<tuple<int, int, int>> G;

  for (int j = 1; j <= n; j++) {

    // G -> G'
    vector<tuple<int, int, int>> H;
    for (const tuple<int, int, int> &idk : G) {
      int i, d, k;
      tie(i, d, k) = idk;
      if (i > 1 && s[i - 2] == s[j - 1]) {
        H.emplace_back(i - 1, d, k);
      }
    }

    // G' -> G''
    deque<tuple<int, int, int>> I;
    int r = -j;
    for (const tuple<int, int, int> &idk : H) {
      int i, d, k;
      tie(i, d, k) = idk;
      if (i - r != d) {
        I.emplace_back(i, i - r, 1);
        if (k > 1) {
          I.emplace_back(i + d, d, k - 1);
        }
      }
      else {
        I.emplace_back(idk);
      }
      r = i + (k - 1) * d;
    }

    if (j > 1 && s[j - 2] == s[j - 1]) {
      I.emplace_back(j - 1, j - 1 - r, 1);
      r = j;
    }
    I.emplace_back(j, j - r, 1);

    G.clear();

    // G'' -> next G
    int ip, dp, kp;
    tie(ip, dp, kp) = I.front(); I.pop_front();
    for (const tuple<int, int, int> &idk : I) {
      int i, d, k;
      tie(i, d, k) = idk;
      if (dp == d) {
        kp += k;
      }
      else {
        G.emplace_back(ip, dp, kp);
        ip = i;
        dp = d;
        kp = k;
      }
    }
    G.emplace_back(ip, dp, kp);

    // calc pl
    for (const tuple<int, int, int> &idk : G) {
      int i, d, k;
      tie(i, d, k) = idk;
      r = i + (k - 1) * d;
      int m = 0;
      if (r - 2 >= 0) m += mana.is_palindrome(0, r - 2);
      if (k > 1 && i - d >= 0) {
        m += gpl[i - d];
      }
      if (d <= i) {
        gpl[i - d] = m;
      }
      pl[j - 1] += m;
    }
  }

  vector<long long> sum_p2(n + 1);
  for (int i = 1; i < n; i++) sum_p2[i + 1] = sum_p2[i] + pl[i];

  long long ans = 0;
  for (int k = 0; k < n - 1; k++) {
    if (mana.is_palindrome(k + 1, n - 1)) {
      ans += sum_p2[k];
    }
  }

  cout << ans << endl;
}
0