結果
問題 | No.599 回文かい |
ユーザー | snrnsidy |
提出日時 | 2021-09-21 13:56:53 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,221 bytes |
コンパイル時間 | 2,094 ms |
コンパイル使用メモリ | 200,524 KB |
実行使用メモリ | 261,112 KB |
最終ジャッジ日時 | 2023-09-16 22:56:20 |
合計ジャッジ時間 | 10,066 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,384 KB |
testcase_04 | AC | 5 ms
15,936 KB |
testcase_05 | AC | 5 ms
13,960 KB |
testcase_06 | AC | 5 ms
16,012 KB |
testcase_07 | AC | 6 ms
18,008 KB |
testcase_08 | AC | 5 ms
16,008 KB |
testcase_09 | AC | 5 ms
13,820 KB |
testcase_10 | AC | 532 ms
174,380 KB |
testcase_11 | AC | 291 ms
178,024 KB |
testcase_12 | AC | 566 ms
208,384 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | AC | 967 ms
246,828 KB |
testcase_17 | MLE | - |
testcase_18 | AC | 2 ms
5,864 KB |
testcase_19 | AC | 3 ms
5,648 KB |
testcase_20 | AC | 2 ms
5,592 KB |
evil_0.txt | WA | - |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MOD = 100003; inline int mod(long long n){ if(n >= 0) return n % MOD; return ((-n/MOD+1)*MOD + n) % MOD; } int arr[10000][10000]; int dp[5005]; int main() { char S[200001]; 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++) { int L1 = i; int R1 = i + j - 1; int R2 = L-1-i; int L2 = R2-j+1; if(L2<=R1) break; if(arr[L1][R1]==arr[L2][R2]) { 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; }