結果
問題 | No.599 回文かい |
ユーザー |
![]() |
提出日時 | 2021-11-25 15:31:12 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,699 ms / 4,000 ms |
コード長 | 687 bytes |
コンパイル時間 | 476 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 98,560 KB |
最終ジャッジ日時 | 2024-06-28 06:57:58 |
合計ジャッジ時間 | 7,583 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
def z_algorithm(s): n = len(s) Z = [0]*n Z[0] = n i = 1 j = 0 while i < n: while i+j < n and s[j] == s[i+j]: j += 1 Z[i] = j if j == 0: i += 1 continue k = 1 while i+k < n and k+Z[k] < j: Z[i+k] = Z[k] k += 1 i += k j -= k return Z s = str(input()) n = len(s) mod = 10**9+7 dp = [1]*(n//2+1) for i in reversed(range(n)): if i >= n-i: continue t = s[i:n-i] Z = z_algorithm(t) for j in range(1, len(t)//2+1): if Z[len(t)-j] == j: dp[i] += dp[i+j] dp[j] %= mod #print(dp) print(dp[0]%mod)