#941253 (C++14) No.599 回文かい

提出ソース

結果

問題	No.599 回文かい
ユーザー	zoidzium
提出日時	2023-12-30 17:22:17
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,781 ms / 4,000 ms
コード長	10,641 bytes
コンパイル時間	2,323 ms
コンパイル使用メモリ	190,716 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-27 16:44:03
合計ジャッジ時間	8,359 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	3 ms 6,940 KB
testcase_05	AC	3 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	3 ms 6,944 KB
testcase_10	AC	5 ms 6,944 KB
testcase_11	AC	4 ms 6,940 KB
testcase_12	AC	11 ms 6,940 KB
testcase_13	AC	17 ms 6,944 KB
testcase_14	AC	1,336 ms 6,940 KB
testcase_15	AC	76 ms 6,940 KB
testcase_16	AC	1,553 ms 6,940 KB
testcase_17	AC	1,781 ms 6,940 KB
testcase_18	AC	2 ms 6,944 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,940 KB
evil_0.txt	AC	564 ms 6,944 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

using ll = long long;
using ull = unsigned long long;
using xy = pair<ll, ll>;
using uxy = pair<ull, ull>;
using zzz = tuple<ll, ll, ll>;

using vl = vector<ll>;
using vul = vector<ull>;
using vxy = vector<xy>;
using vuxy = vector<uxy>;
using vzzz = vector<zzz>;
using vs = vector<string>;

using vvl = vector<vl>;
using vvxy = vector<vxy>;
using vvzzz = vector<vzzz>;

using vvvl = vector<vvl>;
using vvvxy = vector<vvxy>;
using vvvzzz = vector<vvzzz>;

#define rep(i, n) for (long long i = 0; i < (n); i++)
#define cnt(i, n, m) for (long long i = (n); i <= (m); i++)
#define echo(ite, C) for (auto ite = (C).begin(); ite != (C).end(); ite++)
#define recho(ite, C) for (auto ite = (C).rbegin(); ite != (C).rend(); ite++)
#define yn(b) cout << (((b) > 0) ? "Yes" : "No") << endl;
#define nth(a, b) (((a) >> (b)) & 1)

class triHash {
 public:
  static unordered_map<ull, ull> Hs;
  static unordered_map<ull, unordered_map<ull, unordered_map<ull, ull>>> Hs3;

 private:
  static ull Cnt;
  static ull ME31;
  static ull ME30;
  static ull M1;
  static ull M2;
  static ull M3;
  static ull D;
  static ull Inv1;
  static ull Inv2;
  static ull Inv3;

  ull E1 = 0ULL;
  ull E2 = 0ULL;
  ull E3 = 0ULL;
  ull Len = 0ULL;
  ull B1 = 1ULL;
  ull B2 = 1ULL;
  ull B3 = 1ULL;

 public:
  triHash()
      : E1(0ULL), E2(0ULL), E3(0ULL), Len(0), B1(1ULL), B2(1ULL), B3(1ULL) {
    if (Cnt == 0) {
      ME31 = ((1ULL << 31) - 1ULL);
      ME30 = ((1ULL << 30) - 1ULL);
      M1 = ((1ULL << 61) - 1ULL);
      M2 = (2147483647ULL);
      M3 = (1000000007ULL);
      D = (67);
      Inv1 = (triHash::inv61(D));
      Inv2 = (triHash::inv(D, M2));
      Inv3 = (triHash::inv(D, M3));
    }
    Cnt++;
  };
  triHash(const string& S)
      : E1(0ULL), E2(0ULL), E3(0ULL), Len(0), B1(1ULL), B2(1ULL), B3(1ULL) {
    if (Cnt == 0) {
      ME31 = ((1ULL << 31) - 1ULL);
      ME30 = ((1ULL << 30) - 1ULL);
      M1 = ((1ULL << 61) - 1ULL);
      M2 = (2147483647ULL);
      M3 = (1000000007ULL);
      D = (67);
      Inv1 = (triHash::inv61(D));
      Inv2 = (triHash::inv(D, M2));
      Inv3 = (triHash::inv(D, M3));
    }
    Cnt++;
    this->setStr(S);
  };

  static ull inv(const ull& D, const ull M) {
    ull X = 1ULL;
    ull A = D;
    ull N = M - 2ULL;
    while (N > 0) {
      if (N & 1) X = (X * A) % M;
      A = (A * A) % M;
      N /= 2;
    }
    return X;
  };
  static ull inv61(const ull& D) {
    ull X = 1ULL;
    ull A = D;
    ull N = M1 - 2ULL;
    while (N > 0) {
      if (N & 1) X = triHash::mul61(X, A);
      A = triHash::mul61(A, A);
      N /= 2;
    }
    return X;
  };
  static ull mul61(const ull& A, const ull& B) {
    ull Au = A >> 31, Av = A & ME31;
    ull Bu = B >> 31, Bv = B & ME31;
    ull AB = Au * Bv + Av * Bu;
    ull ABu = AB >> 30, ABv = AB & ME30;
    ull X = Au * Bu * 2 + ABu + (ABv << 31) + Av * Bv;
    return mod61(X);
  };
  static ull mod61(const ull& X) {
    ull Xu = X >> 61;
    ull Xv = X & M1;
    ull Y = Xu + Xv;
    if (Y >= M1) Y -= M1;
    return Y;
  };
  static ull CtoUL(const char& C) {
    if (C == ' ') return 0ULL;
    ull X = C + 1 - '0';
    if (C >= 'A') X -= 7;
    if (C >= 'a') X -= 6;
    return X;
  };
  static char ULtoC(const ull& X) {
    if (X == 0ULL) return ' ';
    char C = (char)(X - 1 + '0');
    if (C > '9') C += 7;
    if (C >= 'Z') C += 6;
    return C;
  };

  vul getE() {
    vul ANS(3);
    ANS[0] = this->E1;
    ANS[1] = this->E2;
    ANS[2] = this->E3;
    return ANS;
  }
  vul getB() {
    vul ANS(3);
    ANS[0] = this->B1;
    ANS[1] = this->B2;
    ANS[2] = this->B3;
    return ANS;
  }
  ull getLen() { return this->Len; };
  string getStr() {
    ull TMP = this->E1;
    string S;
    rep(i, this->Len) {
      ull X = TMP % D;
      S.push_back(triHash::ULtoC(X));

      TMP = mod61(M1 + TMP - X);
      TMP = triHash::mul61(TMP, this->Inv1);
    }
    return S;
  };

  void push_back(const char& C) {
    Len++;
    ull E = triHash::CtoUL(C);
    E1 = mod61(E1 + triHash::mul61(E, B1));
    E2 = (E2 + ((E * B2) % M2));
    E3 = (E3 + ((E * B3) % M3));
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;

    B1 = triHash::mul61(B1, D);
    B2 = (B2 * D) % M2;
    B3 = (B3 * D) % M3;
  };
  void push_front(const char& C) {
    Len++;
    ull E = triHash::CtoUL(C);
    E1 = mod61(triHash::mul61(E1, D) + E);
    E2 = (((E2 * D) % M2) + E);
    E3 = (((E3 * D) % M3) + E);
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;

    B1 = triHash::mul61(B1, D);
    B2 = (B2 * D) % M2;
    B3 = (B3 * D) % M3;
    if (B2 >= M2) B2 -= M2;
    if (B3 >= M3) B3 -= M3;
  };
  void setStr(const string& S) {
    for (auto ite = S.begin(), end = S.end(); ite != end; ite++)
      push_back((char)*ite);
  };
  void pop_back(const char& C) {
    if (Len == 0) return;
    Len--;
    ull E = triHash::CtoUL(C);
    B1 = triHash::mul61(B1, Inv1);
    B2 = (B2 * Inv2) % M2;
    B3 = (B3 * Inv3) % M3;

    E1 = mod61(M1 + E1 - triHash::mul61(E, B1));
    E2 = (M2 + E2 - ((E * B2) % M2));
    E3 = (M3 + E3 - ((E * B3) % M3));
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;
  }
  void pop_front(const char& C) {
    if (Len == 0) return;
    Len--;
    ull E = triHash::CtoUL(C);

    E1 = (M1 + E1 - E);
    if (E1 >= M1) E1 -= M1;
    E1 = triHash::mul61(E1, Inv1);
    E2 = (((M2 + E2 - E) % M2) * Inv2) % M2;
    E3 = (((M3 + E3 - E) % M3) * Inv3) % M3;

    B1 = triHash::mul61(B1, Inv1);
    B2 = (B2 * Inv2) % M2;
    B3 = (B3 * Inv3) % M3;
  };

  void addNum(const ull& X) {
    E1 = mod61(E1 + X);
    E2 = (E2 + X);
    E3 = (E3 + X);
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;
  };
  void subNum(const ull& X) {
    E1 = mod61(M1 + E1 - X);
    E2 = (M2 + E2 - X);
    E3 = (M3 + E3 - X);
    if (E2 >= M2) E2 -= M2;
    if (E3 >= M3) E3 -= M3;
  };
  void marge(triHash& A, triHash& B) {
    vul Ve1 = A.getE();
    vul Ve2 = B.getE();
    vul Vb1 = A.getB();
    vul Vb2 = B.getB();
    ull Len1 = A.getLen();
    ull Len2 = B.getLen();
    ull Len = A.getLen();
    this->E1 = mul61(Ve2[0], Vb1[0]);
    this->E1 += Ve1[0];
    if (this->E1 >= M1) this->E1 -= M1;
    this->B1 = mul61(Vb1[0], Vb2[0]);

    this->E2 = (Ve2[1] * Vb1[1]) % M2;
    this->E2 += Ve1[1];
    if (this->E2 >= M2) this->E2 -= M2;
    this->B2 = (Vb1[1] * Vb2[1]) % M2;

    this->E3 = (Ve2[2] * Vb1[2]) % M3;
    this->E3 += Ve1[2];
    if (this->E3 >= M3) this->E3 -= M3;
    this->B3 = (Vb1[2] * Vb2[2]) % M3;

    this->Len = Len1 + Len2;
  };
  bool same(triHash& Comp) {
    vul Vec1 = this->getE();
    vul Vec2 = Comp.getE();
    return (Vec1 == Vec2);
  }
  bool same1(triHash& Comp) {
    vul Vec1 = this->getE();
    vul Vec2 = Comp.getE();
    return (Vec1[0] == Vec2[0]);
  }

  void show() {
    printf("--- SHOW ---\n");
    printf("Len=%lld\n", this->Len);

    printf("[%s]\n", this->getStr().c_str());
    printf(" B1=%019lld\n", E1);
    printf(" B2=%019lld\n", E2);
    printf(" B3=%019lld\n", E3);
  };

  bool Hmake(const ull& X) { return triHash::Href(X, false); };
  bool Hset(const ull& X) { return triHash::Href(X, true); };
  bool Href(const ull& X, const bool& B) {
    auto HH1 = triHash::Hs3.find(this->E1);
    if (HH1 == triHash::Hs3.end()) {
      triHash::Hs3.emplace(this->E1,
                           unordered_map<ull, unordered_map<ull, ull>>());
      HH1 = triHash::Hs3.find(this->E1);
    }

    auto HH2 = HH1->second.find(this->E2);
    if (HH2 == HH1->second.end()) {
      HH1->second.emplace(this->E2, unordered_map<ull, ull>());
      HH2 = HH1->second.find(this->E2);
    }

    auto HH3 = HH2->second.find(this->E3);
    if (HH3 == HH2->second.end()) {
      HH2->second.emplace(this->E3, X);
      return true;
    }
    if (!B) return false;
    HH3->second = X;
    return true;
  };
  pair<bool, ull> Hfind() {
    auto HH1 = triHash::Hs3.find(this->E1);
    if (HH1 == triHash::Hs3.end()) return make_pair(false, 0ULL);
    auto HH2 = HH1->second.find(this->E2);
    if (HH2 == HH1->second.end()) return make_pair(false, 0ULL);
    auto HH3 = HH2->second.find(this->E3);
    if (HH3 == HH2->second.end()) return make_pair(false, 0ULL);
    return make_pair(true, HH3->second);
  }

  bool Hmake1(const ull& X) { return triHash::Href1(X, false); };
  bool Hset1(const ull& X) { return triHash::Href1(X, true); };
  bool Href1(const ull& X, const bool& B) {
    auto HH1 = triHash::Hs.find(this->E1);
    if (HH1 == triHash::Hs.end()) {
      triHash::Hs.emplace(this->E1, X);
      return true;
    }
    if (!B) return false;
    HH1->second = X;
    return true;
  };
  pair<bool, ull> Hfind1() {
    auto HH1 = triHash::Hs.find(this->E1);
    if (HH1 == triHash::Hs.end()) return make_pair(false, 0ULL);
    return make_pair(true, HH1->second);
  }
};
unordered_map<ull, ull> triHash::Hs;
unordered_map<ull, unordered_map<ull, unordered_map<ull, ull>>> triHash::Hs3;
ull triHash::Cnt = 0;
ull triHash::ME31;
ull triHash::ME30;
ull triHash::M1;
ull triHash::M2;
ull triHash::M3;
ull triHash::D;
ull triHash::Inv1;
ull triHash::Inv2;
ull triHash::Inv3;

#define Mod 1000000007

int main() {
  string S;
  cin >> S;
  ll N = S.size();
  vl DP(N, -1);

  function<ll(ll, ll)> Func = [&Func, &S, &DP, &N](const ll& L,
                                                   const ll& R) -> ll {
    if (DP[L] != -1) return DP[L];
    if (L == R) {
      DP[L] = 1;
      return DP[L];
    }
    if ((L + 1) == R) {
      DP[L] = 1;
      return DP[L];
    }

    // cout << "[" << L << " " << R << ")" << endl;
    triHash Hf;
    triHash Hb;
    DP[L] = 1;
    cnt(i, L, N - 1) {
      ll j = N - 1 - i;
      // cout << "@L=" << L << " i=" << i << " j=" << j << endl;
      if (i >= j) break;

      Hf.push_front(S[j]);
      Hb.push_back(S[i]);
      if (Hf.same(Hb)) {
        // cout << "[" << L << "][" << Hf.getStr() << "] (" << i + 1 << " " << j
        //      << ")" << endl;
        DP[L] = (DP[L] + Func(i + 1, j)) % Mod;
      }
      // cout << " DP[" << L << "]=" << DP[L] << endl;
    }
    // cout << " [" << L << " " << R << ") = " << DP[L][R] << endl;
    return DP[L];
  };
  cout << Func(0, N) << endl;
  rep(i, N) {
    ll j = N - 1 - i;
    // cout << "[" << i << "]=" << DP[i] << endl;
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード