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 で動いてたので本番では定数倍高速化に走ってしまったが、普通に計算量落とせた。