結果
| 問題 | No.599 回文かい |
| ユーザー |
 zoidzium
|
| 提出日時 | 2023-12-30 17:22:17 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 22 |
ソースコード
#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 1000000007int 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;}