結果
問題 | No.599 回文かい |
ユーザー |
![]() |
提出日時 | 2022-06-03 14:19:26 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 168 ms / 4,000 ms |
コード長 | 1,329 bytes |
コンパイル時間 | 3,285 ms |
コンパイル使用メモリ | 128,896 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-21 02:17:52 |
合計ジャッジ時間 | 2,820 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <iostream> #include <cmath> #include <vector> using ll = long long; using namespace std; struct RollingHash { static constexpr int M = 2; static constexpr long long MODS[M] = {999999937, 1000000007}; static constexpr long long BASE = 9973; vector<long long> powb[M], hash[M]; int n; RollingHash() {} RollingHash(const string& str) {init(str);} void init(const string& str) { n = str.size(); for (int k = 0; k < M; k++) { powb[k].resize(n+1, 1); hash[k].resize(n+1, 0); for (int i = 0; i < n; i++) { hash[k][i+1] = (hash[k][i] * BASE + str[i]) % MODS[k]; powb[k][i+1] = powb[k][i] * BASE % MODS[k]; } } } long long get(int l, int r, int k) { long long res = hash[k][r] - hash[k][l] * powb[k][r-l] % MODS[k]; if (res < 0) res += MODS[k]; return res; } }; bool match(RollingHash& rh1, ll l1, ll r1, RollingHash& rh2, ll l2, ll r2) { bool res = true; for (int k = 0; k < RollingHash::M; k++) { res &= rh1.get(l1, r1, k) == rh2.get(l2, r2, k); } return res; } ll M = pow(10, 9) + 7; int main() { string s; cin >> s; ll n = s.size(); RollingHash h(s); vector<ll> dp(n/2 + 1, 0); dp[n/2] = 1; for (ll i = n/2 - 1; i >= 0; i--) { dp[i] = 1; for (ll l = i+1; l <= n/2; l++) { if (match(h, i, l, h, n-l, n-i)) (dp[i] += dp[l]) %= M; } } cout << dp[0] << endl; }