結果
問題 | No.599 回文かい |
ユーザー |
|
提出日時 | 2017-11-24 22:59:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,436 ms / 4,000 ms |
コード長 | 814 bytes |
コンパイル時間 | 1,608 ms |
コンパイル使用メモリ | 169,428 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-11-27 07:51:23 |
合計ジャッジ時間 | 8,955 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007; string s; int n; ll dp[10005]; int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> s; n = s.length(); dp[(n - 1) / 2] = 1; if (n % 2 == 0) dp[(n - 1) / 2] += (s[(n - 1) / 2] == s[(n - 1) / 2 + 1]); for (int i = (n - 1) / 2 - 1; i >= 0; i--) { dp[i] = 1; string sl = "", sr = ""; for (int j = i + 1; j <= (n - 1) / 2; j++) { sl += s[j - 1]; sr = s[n - j] + sr; if (sl == sr) (dp[i] += dp[j]) %= MOD; } if (n % 2 == 0) { sl += s[(n - 1) / 2]; sr = s[(n - 1) / 2 + 1] + sr; if (sl == sr) (dp[i] += 1) %= MOD; } } cout << dp[0] << endl; return 0; }