#578109 (C++17) No.599 回文かい

• 問題: No.599 回文かい
• ユーザー: RTnF
• 提出日時: 2020-11-09 23:27:34
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 69 ms / 4,000 ms
• コード長: 14,903 bytes
• コンパイル時間: 2,940 ms
• コンパイル使用メモリ: 236,016 KB
• 実行使用メモリ: 35,192 KB
• 最終ジャッジ日時: 2024-07-22 16:24:18
• 合計ジャッジ時間: 4,297 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	11 ms; 34,644 KB
testcase_01	AC	12 ms; 34,640 KB
testcase_02	AC	11 ms; 34,640 KB
testcase_03	AC	11 ms; 34,644 KB
testcase_04	AC	11 ms; 34,772 KB
testcase_05	AC	12 ms; 34,772 KB
testcase_06	AC	11 ms; 34,772 KB
testcase_07	AC	12 ms; 34,640 KB
testcase_08	AC	12 ms; 34,772 KB
testcase_09	AC	12 ms; 34,644 KB
testcase_10	AC	37 ms; 35,156 KB
testcase_11	AC	26 ms; 35,032 KB
testcase_12	AC	38 ms; 35,192 KB
testcase_13	AC	28 ms; 34,896 KB
testcase_14	AC	53 ms; 35,028 KB
testcase_15	AC	60 ms; 35,156 KB
testcase_16	AC	64 ms; 35,152 KB
testcase_17	AC	69 ms; 35,028 KB
testcase_18	AC	11 ms; 34,772 KB
testcase_19	AC	11 ms; 34,772 KB
testcase_20	AC	12 ms; 34,772 KB
evil_0.txt	AC	52 ms; 35,128 KB

ソースコード

#pragma region template
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
// using cpp_int = boost::multiprecision::cpp_int;
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vld = vector<ld>;
using vvld = vector<vld>;
using vvvld = vector<vvld>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
template <typename T>
using pqrev = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, n) for (ll i = 0, i##_end = (n); i < i##_end; i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for (ll i = (a), i##_end = (b); i < i##_end; i++)
#define reprb(i, a, b) for (ll i = (b)-1, i##_end = (a); i >= i##_end; i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif
constexpr ll INF = 1e+18;
constexpr ld EPS = 1e-12L;
constexpr ld PI = 3.14159265358979323846L;
template <typename T>
constexpr T local([[maybe_unused]] const T &lcl, [[maybe_unused]] const T &oj) {
#ifdef OJ_LOCAL
  return lcl;
#else
  return oj;
#endif
}
template <typename S, typename T>
constexpr bool chmax(S &a, const T &b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename S, typename T>
constexpr bool chmin(S &a, const T &b) {
  if (b < a) {
    a = b;
    return 1;
  }
  return 0;
}
template <typename T>
T max(const vector<T> &x) {
  return *max_element(ALL(x));
}
template <typename T>
T min(const vector<T> &x) {
  return *min_element(ALL(x));
}
template <typename T>
pair<T, int> argmax(const vector<T> &x) {
  int idx = 0;
  T m = x[0];
  repr(i, 1, SZ(x)) {
    if (chmax(m, x[i])) idx = i;
  }
  return {m, idx};
}
template <typename T>
pair<T, int> argmin(const vector<T> &x) {
  int idx = 0;
  T m = x[0];
  repr(i, 1, SZ(x)) {
    if (chmin(m, x[i])) idx = i;
  }
  return {m, idx};
}
template <typename T>
T sum(const vector<T> &x) {
  return accumulate(ALL(x), T(0));
}
// last param -> T
template <typename T>
vector<T> makev(size_t a, T b) {
  return vector<T>(a, b);
}
template <typename... Args>
auto makev(size_t sz, Args... args) {
  return vector<decltype(makev(args...))>(sz, makev(args...));
}

template <typename T>
bool print_(const T &a) {
  cout << a;
  return true;
}
template <typename T>
bool print_(const vector<T> &vec) {
  for (auto &a : vec) {
    cout << a;
    if (&a != &vec.back()) cout << " ";
  }
  return false;
}
template <typename T>
bool print_(const vector<vector<T>> &vv) {
  for (auto &v : vv) {
    for (auto &a : v) {
      cout << a;
      if (&a != &v.back()) cout << " ";
    }
    if (&v != &vv.back()) cout << "\n";
  }
  return false;
}
void print() { cout << "\n"; }
template <typename Head, typename... Tail>
void print(Head &&head, Tail &&... tail) {
  bool f = print_(head);
  if (sizeof...(tail) != 0) cout << (f ? " " : "\n");
  print(forward<Tail>(tail)...);
}
#pragma endregion

//*
constexpr ll MOD = 1e9 + 7;
/*/
constexpr ll MOD = 998244353;
//*/

// ModInt
// 参考：https://ei1333.github.io/luzhiled/snippets/math/mod-int.html
// modはコンパイル時に決定
template <ll mod>
struct ModInt {
  ll x;
  ModInt() : x(0) {}
  ModInt(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
  constexpr ModInt &operator+=(const ModInt &p) {
    if ((x += p.x) >= mod) x -= mod;
    return *this;
  }
  constexpr ModInt &operator-=(const ModInt &p) {
    if ((x += mod - p.x) >= mod) x -= mod;
    return *this;
  }
  constexpr ModInt &operator*=(const ModInt &p) {
    x = x * p.x % mod;
    return *this;
  }
  constexpr ModInt &operator/=(const ModInt &p) {
    *this *= p.inverse();
    return *this;
  }
  constexpr ModInt operator-() { return ModInt(-x); }
  constexpr ModInt operator+() { return ModInt(x); }
  constexpr ModInt &operator++() {
    x++;
    if (x == mod) x = 0;
    return *this;
  }
  constexpr ModInt &operator--() {
    if (x == 0) x = mod;
    x--;
    return *this;
  }
  constexpr ModInt operator++(int) {
    ModInt result = *this;
    ++*this;
    return result;
  }
  constexpr ModInt operator--(int) {
    ModInt result = *this;
    --*this;
    return result;
  }
  friend constexpr ModInt operator+(const ModInt &lhs, const ModInt &rhs) {
    return ModInt(lhs) += rhs;
  }
  friend constexpr ModInt operator-(const ModInt &lhs, const ModInt &rhs) {
    return ModInt(lhs) -= rhs;
  }
  friend constexpr ModInt operator*(const ModInt &lhs, const ModInt &rhs) {
    return ModInt(lhs) *= rhs;
  }
  friend constexpr ModInt operator/(const ModInt &lhs, const ModInt &rhs) {
    return ModInt(lhs) /= rhs;
  }
  friend constexpr bool operator==(const ModInt &lhs, const ModInt &rhs) {
    return lhs.x == rhs.x;
  }
  friend constexpr bool operator!=(const ModInt &lhs, const ModInt &rhs) {
    return lhs.x != rhs.x;
  }
  constexpr ModInt inverse() const {
    ll a = x, b = mod, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }
  constexpr ModInt pow(ll n) {
    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }
  friend ostream &operator<<(ostream &os, const ModInt &p) { return os << p.x; }
  friend istream &operator>>(istream &is, ModInt &a) {
    ll t;
    is >> t;
    a = ModInt<mod>(t);
    return (is);
  }
};

using mint = ModInt<MOD>;
using vm = vector<mint>;
using vvm = vector<vm>;

constexpr int MAX_FAC = 2000010;
mint fac[MAX_FAC], facinv[MAX_FAC];
void combInit() {
  fac[0] = mint(1);
  for (int i = 0; i < MAX_FAC - 1; i++) { fac[i + 1] = fac[i] * (i + 1); }
  facinv[MAX_FAC - 1] = fac[MAX_FAC - 1].inverse();
  for (int i = MAX_FAC - 2; i >= 0; i--) {
    facinv[i] = facinv[i + 1] * (i + 1);
  }
}
mint comb(const ll a, const ll b) {
  assert(a < MAX_FAC);
  assert(b < MAX_FAC);
  if (a < 0 || b < 0 || b > a) { return mint(0); }
  mint ret(1);
  ret *= fac[a];
  ret *= facinv[b];
  ret *= facinv[a - b];
  return ret;
}
mint multicomb(const ll a, const ll b) { return comb(a + b - 1, b); }


#define PR(f)                                                                  \
  do {                                                                         \
    cout << ((f) ? "Yes" : "No") << "\n";                                      \
    return;                                                                    \
  } while (0)

namespace internal {

vector<int> sa_naive(const vector<int> &s) {
  int n = int(s.size());
  vector<int> sa(n);
  iota(sa.begin(), sa.end(), 0);
  sort(sa.begin(), sa.end(), [&](int l, int r) {
    if (l == r) return false;
    while (l < n && r < n) {
      if (s[l] != s[r]) return s[l] < s[r];
      l++;
      r++;
    }
    return l == n;
  });
  return sa;
}

vector<int> sa_doubling(const vector<int> &s) {
  int n = int(s.size());
  vector<int> sa(n), rnk = s, tmp(n);
  iota(sa.begin(), sa.end(), 0);
  for (int k = 1; k < n; k *= 2) {
    auto cmp = [&](int x, int y) {
      if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
      int rx = x + k < n ? rnk[x + k] : -1;
      int ry = y + k < n ? rnk[y + k] : -1;
      return rx < ry;
    };
    sort(sa.begin(), sa.end(), cmp);
    tmp[sa[0]] = 0;
    for (int i = 1; i < n; i++) {
      tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
    }
    swap(tmp, rnk);
  }
  return sa;
}

// SA-IS, linear-time suffix array construction
// Reference:
// G. Nong, S. Zhang, and W. H. Chan,
// Two Efficient Algorithms for Linear Time Suffix Array Construction
template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
vector<int> sa_is(const vector<int> &s, int upper) {
  int n = int(s.size());
  if (n == 0) return {};
  if (n == 1) return {0};
  if (n == 2) {
    if (s[0] < s[1]) {
      return {0, 1};
    } else {
      return {1, 0};
    }
  }
  if (n < THRESHOLD_NAIVE) { return sa_naive(s); }
  if (n < THRESHOLD_DOUBLING) { return sa_doubling(s); }

  vector<int> sa(n);
  vector<bool> ls(n);
  for (int i = n - 2; i >= 0; i--) {
    ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
  }
  vector<int> sum_l(upper + 1), sum_s(upper + 1);
  for (int i = 0; i < n; i++) {
    if (!ls[i]) {
      sum_s[s[i]]++;
    } else {
      sum_l[s[i] + 1]++;
    }
  }
  for (int i = 0; i <= upper; i++) {
    sum_s[i] += sum_l[i];
    if (i < upper) sum_l[i + 1] += sum_s[i];
  }

  auto induce = [&](const vector<int> &lms) {
    fill(sa.begin(), sa.end(), -1);
    vector<int> buf(upper + 1);
    copy(sum_s.begin(), sum_s.end(), buf.begin());
    for (auto d : lms) {
      if (d == n) continue;
      sa[buf[s[d]]++] = d;
    }
    copy(sum_l.begin(), sum_l.end(), buf.begin());
    sa[buf[s[n - 1]]++] = n - 1;
    for (int i = 0; i < n; i++) {
      int v = sa[i];
      if (v >= 1 && !ls[v - 1]) { sa[buf[s[v - 1]]++] = v - 1; }
    }
    copy(sum_l.begin(), sum_l.end(), buf.begin());
    for (int i = n - 1; i >= 0; i--) {
      int v = sa[i];
      if (v >= 1 && ls[v - 1]) { sa[--buf[s[v - 1] + 1]] = v - 1; }
    }
  };

  vector<int> lms_map(n + 1, -1);
  int m = 0;
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) { lms_map[i] = m++; }
  }
  vector<int> lms;
  lms.reserve(m);
  for (int i = 1; i < n; i++) {
    if (!ls[i - 1] && ls[i]) { lms.push_back(i); }
  }

  induce(lms);

  if (m) {
    vector<int> sorted_lms;
    sorted_lms.reserve(m);
    for (int v : sa) {
      if (lms_map[v] != -1) sorted_lms.push_back(v);
    }
    vector<int> rec_s(m);
    int rec_upper = 0;
    rec_s[lms_map[sorted_lms[0]]] = 0;
    for (int i = 1; i < m; i++) {
      int l = sorted_lms[i - 1], r = sorted_lms[i];
      int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
      int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
      bool same = true;
      if (end_l - l != end_r - r) {
        same = false;
      } else {
        while (l < end_l) {
          if (s[l] != s[r]) { break; }
          l++;
          r++;
        }
        if (l == n || s[l] != s[r]) same = false;
      }
      if (!same) rec_upper++;
      rec_s[lms_map[sorted_lms[i]]] = rec_upper;
    }

    auto rec_sa = sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);

    for (int i = 0; i < m; i++) { sorted_lms[i] = lms[rec_sa[i]]; }
    induce(sorted_lms);
  }
  return sa;
}

} // namespace internal

vector<int> suffix_array(const vector<int> &s, int upper) {
  assert(0 <= upper);
  for (int d : s) { assert(0 <= d && d <= upper); }
  auto sa = internal::sa_is(s, upper);
  return sa;
}

template <class T>
vector<int> suffix_array(const vector<T> &s) {
  int n = int(s.size());
  vector<int> idx(n);
  iota(idx.begin(), idx.end(), 0);
  sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
  vector<int> s2(n);
  int now = 0;
  for (int i = 0; i < n; i++) {
    if (i && s[idx[i - 1]] != s[idx[i]]) now++;
    s2[idx[i]] = now;
  }
  return internal::sa_is(s2, now);
}

vector<int> suffix_array(const string &s) {
  int n = int(s.size());
  vector<int> s2(n);
  for (int i = 0; i < n; i++) { s2[i] = s[i]; }
  return internal::sa_is(s2, 255);
}

// Reference:
// T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
// Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
// Applications
template <class T>
vector<int> lcp_array(const vector<T> &s, const vector<int> &sa) {
  int n = int(s.size());
  assert(n >= 1);
  vector<int> rnk(n);
  for (int i = 0; i < n; i++) { rnk[sa[i]] = i; }
  vector<int> lcp(n - 1);
  int h = 0;
  for (int i = 0; i < n; i++) {
    if (h > 0) h--;
    if (rnk[i] == 0) continue;
    int j = sa[rnk[i] - 1];
    for (; j + h < n && i + h < n; h++) {
      if (s[j + h] != s[i + h]) break;
    }
    lcp[rnk[i] - 1] = h;
  }
  return lcp;
}

vector<int> lcp_array(const string &s, const vector<int> &sa) {
  int n = int(s.size());
  vector<int> s2(n);
  for (int i = 0; i < n; i++) { s2[i] = s[i]; }
  return lcp_array(s2, sa);
}

// Disjoint Sparse Table
// opは半群で結合律を満たす
// 構築 O(N log N) クエリ O(1)
template <typename S, S (*op)(S, S)>
struct DisjointSparseTable {
  DisjointSparseTable(const vector<S> &v) : n(v.size()) {
    log = 1;
    while ((1 << log) < n) log++;
    table.assign(log, v);
    for (int i = 1; i < log; i++) {
      int block_size = 1 << i;
      int en;
      bool rev = true;
      for (int st = 0; st < n; st += block_size) {
        en = min(st + block_size - 1, n - 1);
        if (rev) {
          for (int j = en - 1; j >= st; j--) {
            table[i][j] = op(table[i][j], table[i][j + 1]);
          }
        } else {
          for (int j = st + 1; j <= en; j++) {
            table[i][j] = op(table[i][j - 1], table[i][j]);
          }
        }
        rev = !rev;
      }
    }
  }
  // [l, r) 0 <= l < r <= n
  S fold(int l, int r) {
    assert(0 <= l && l < r && r <= n);
    r--;
    if (l == r) return table[0][l];
    int i = 31 - __builtin_clz(l ^ r);
    return op(table[i][l], table[i][r]);
  }

private:
  vector<vector<S>> table;
  int n, log;
};

ll llmin(ll a, ll b) { return min(a, b); }
ll llmax(ll a, ll b) { return max(a, b); }
int intmin(int a, int b) { return min(a, b); }
int intmax(int a, int b) { return max(a, b); }

// ソート結果を配列のインデックスで得る
// 配列自体はソートされない
// {9, 5, 1, 3, 7} -> {2, 3, 1, 4, 0}
template <typename T>
vector<int> argSort(const vector<T> &vec) {
  vector<int> idx(vec.size());
  iota(idx.begin(), idx.end(), 0);
  stable_sort(idx.begin(), idx.end(),
              [&](int l, int r) { return vec[l] < vec[r]; });
  return idx;
}


void solve() {
  string s;
  cin >> s;
  ll n = SZ(s);
  auto sa = suffix_array(s);
  auto lcpa = lcp_array(s, sa);
  auto argsa = argSort(sa);
  dump(sa, lcpa);
  DisjointSparseTable<int, intmin> sp(lcpa);
  {
    ll i = 0;
    ll c = 1;
    repb(j, n){
      if(i >= j) break;
      ll x = argsa[i];
      ll y = argsa[j];
      ll lc = 0;
      if(x < y) lc = sp.fold(x, y);
      if(y < x) lc = sp.fold(y, x);
      dump(argsa[i], argsa[j], s.substr(i), s.substr(j), lc, c);
      if(lc >= c){
        dump(s.substr(j, c), c);
        i += c;
        c = 0;
      }
      c++;
    }
  }
  vm dp(n/2+1, 0);
  dp[0] = 1;
  rep(i, n/2){
    repr(j, 1, n/2-i+1){
      ll x = argsa[i];
      ll y = argsa[n-i-j];
      if(x != y && sp.fold(min(x, y), max(x, y)) >= j){
        dump(i, j, s.substr(i), s.substr(n-i-j), sp.fold(min(x, y), max(x, y)));
        dp[i+j] += dp[i];
      }
    }
  }
  print(sum(dp));
  dump(dp);
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  //*
  solve();
  /*/
  ll _cases;
  cin >> _cases;
  while (_cases--) solve();
  //*/
}