結果
問題 | No.599 回文かい |
ユーザー |
|
提出日時 | 2017-12-27 03:04:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 4,000 ms |
コード長 | 1,044 bytes |
コンパイル時間 | 2,157 ms |
コンパイル使用メモリ | 197,168 KB |
最終ジャッジ日時 | 2025-01-05 06:34:04 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> const int MOD = 1e9 + 7; const int B = 311; int Dp(const std::string &s) { std::vector<int> pb(s.size() + 1); { for (int i = pb[0] = 1; i <= s.size(); ++i) { pb[i] = 1LL * pb[i - 1] * B % MOD; } } std::vector<int> ph(s.size() + 1); { for (int i = 0; i < s.size(); ++i) { ph[i + 1] = (1LL * ph[i] * B + s[i]) % MOD; } } std::function<int(const std::vector<int>&, int, int)> gh = [&](const std::vector<int> &ph, int lb, int rb) { return ((ph[rb] - 1LL * ph[lb] * pb[rb - lb]) % MOD + MOD) % MOD; }; std::vector<int> dp(s.size() / 2 + 1); for (int i = dp[0] = 1; i <= s.size() / 2; ++i) { for (int j = 0; j < i; ++j) { if (gh(ph, j, i) == gh(ph, s.size() - i, s.size() - j)) { (dp[i] += dp[j]) %= MOD; } } } return std::accumulate(dp.begin(), dp.end(), 0, [&](int x, int y) { return (x + y) % MOD; }); } signed main() { std::ios::sync_with_stdio(false); std::string S; std::cin >> S; std::cout << Dp(S) << std::endl; return 0; }