結果
問題 |
No.599 回文かい
|
ユーザー |
|
提出日時 | 2017-11-24 22:41:42 |
言語 | D (dmd 2.109.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 878 bytes |
コンパイル時間 | 1,022 ms |
コンパイル使用メモリ | 112,352 KB |
実行使用メモリ | 14,008 KB |
最終ジャッジ日時 | 2024-06-12 22:37:48 |
合計ジャッジ時間 | 6,587 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 TLE * 1 -- * 11 |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm;import std.typecons, std.range, std.random, std.math, std.container;import std.numeric, std.bigint, core.bitop;const long MOD = 10^^9 + 7;void main() {auto S = readln.chomp;auto N = S.length.to!int;int[][string] hoge;foreach (i; 0..N)foreach (j; i+1..N+1)hoge[S[i..j]] ~= i;auto mem = new long[](N);mem.fill(-1);long dfs(int l) {if (l >= N/2)return 0;if (mem[l] >= 0)return mem[l];int r = N - l - 1;long ret = 0;foreach (i; l..N/2) {if (S[l..i+1] in hoge && !(hoge[S[l..i+1]].assumeSorted.equalRange(N-i-1).empty)) {(ret += dfs(i+1) + 1) %= MOD;}}mem[l] = ret;return ret;}writeln(dfs(0)+1);}