結果
問題 | No.599 回文かい |
ユーザー | snrnsidy |
提出日時 | 2021-09-21 14:07:34 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,479 bytes |
コンパイル時間 | 1,861 ms |
コンパイル使用メモリ | 200,224 KB |
実行使用メモリ | 173,292 KB |
最終ジャッジ日時 | 2023-09-16 23:19:49 |
合計ジャッジ時間 | 10,787 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
8,756 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 4 ms
10,084 KB |
testcase_05 | AC | 3 ms
8,060 KB |
testcase_06 | AC | 4 ms
10,040 KB |
testcase_07 | AC | 4 ms
10,104 KB |
testcase_08 | AC | 4 ms
10,056 KB |
testcase_09 | AC | 3 ms
8,080 KB |
testcase_10 | AC | 379 ms
125,660 KB |
testcase_11 | AC | 226 ms
107,144 KB |
testcase_12 | AC | 429 ms
146,512 KB |
testcase_13 | AC | 253 ms
113,644 KB |
testcase_14 | AC | 628 ms
167,048 KB |
testcase_15 | AC | 728 ms
171,024 KB |
testcase_16 | TLE | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
evil_0.txt | -- | - |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MOD = 10007; inline int mod(long long n){ if(n >= 0) return n % MOD; return ((-n/MOD+1)*MOD + n) % MOD; } short arr[10000][10000]; int dp[5005]; bool issame = true; int L1,R1,L2,R2; char S[200001]; int main() { scanf("%s", S); int L = strlen(S); for(int mid=1;mid<=L;mid++) { int H = 0, power = 1; for(int i=0; i<=L-mid; i++){ if(i == 0){ for(int j=0; j<mid; j++){ H = mod(H + 1LL*S[mid-1-j]*power); if(j < mid-1) power = mod(power*2); } } else H = mod(2*(H - 1LL*S[i-1]*power) + S[i+mid-1]); arr[i][i+mid-1] = H; } } dp[0] = 1; for(int i=0;i<=(L/2);i++) { for(int j=1;j<=L;j++) { L1 = i; R1 = i + j - 1; R2 = L-1-i; L2 = R2-j+1; if(L2<=R1) break; issame = true; if(arr[L1][R1]==arr[L2][R2]) { for(int k=0;k<j;k++) { if(S[L1+k]!=S[L2+k]) { issame = false; break; } } if(issame) { dp[R1+1] += dp[i]; dp[R1+1]%=1000000007; } } } } long long int res = 0; for(int i=0;i<=(L/2);i++) { res += dp[i]; res%=(1000000007); } cout << res << '\n'; return 0; }