CSAcademy Round #9: 101 Palindromes
https://csacademy.com/contest/archive/#task/101-palindromes/
解法
区間 DP する。
- dp[ L ][ R ][ m ][ k ] := 区間 [L,R] にある回文のうち、mod 101 が m で長さが k であるようなものの個数
10k は mod 101 では 1→10→100→91→1→…のように変化し、その周期は 4 である。よって長さは mod 4 だけ持てばいい。
区間 [L,R] の回文は以下の 4 パターンに分類できる。
- $S_L$
- $S_L-S_X$
- $S_L-dp[L+1][X-1]-S_X$
- $dp[L+1][R]$
ただし X は [L+1,R] にある S[L]=S[X] であるような位置とする。これを愚直に計算しようと思うと 200*200*101*4*200 程度のループが必要になるが、実装を工夫すれば最後の 200 は落とせる。
200*200*101*4*200 が 1200ms で動いてたので本番では定数倍高速化に走ってしまったが、普通に計算量落とせた。