https://codeforces.com/contest/835/problem/D

題意：

一個(gè)字符是 1 級(jí)回文。一個(gè)字符串是 k 級(jí)回文當(dāng)且僅當(dāng)下面條件成立：

1. 它的左邊一半與右邊一半對(duì)稱，如果字符串長(zhǎng)度為7，則一半長(zhǎng)度為3；

2. 它的左邊和右邊一半都是非空的 k?1 回文。

左半字符串 t 的前綴長(zhǎng)度為 ?t|2?，右半字符串是同樣長(zhǎng)度的后綴。?t|2? 是字符串 t 的長(zhǎng)度除以 2 以后向下取整。

Note that each substring is counted as many times as it appears in the string.

如果一個(gè)回文子串出現(xiàn)多次，則也被計(jì)數(shù)多次。

題解：

使用區(qū)間 dp 進(jìn)行計(jì)算。設(shè) dp[L][r] 表示區(qū)間 [L,r] 是幾級(jí)回文串。

如果不是回文串則值為 0。先預(yù)處理出 dp[i][i] 的值。之后，轉(zhuǎn)移方程為：

1. 若 s[L]≠s[r] 或者 dp[L+1][r?1]=0，則 dp[L][r]=0。

2. 若 s[L]=s[r] 且 dp[L+1][r?1]≠0，那么 dp[L][r] = dp[L][L + len / 2 - 1]+1

ans 數(shù)組先記錄每級(jí)回文串有多少個(gè)，然后再加上所有大于當(dāng)前回文串級(jí)數(shù)的回文串個(gè)數(shù)。

例如：2級(jí)回文串 也是 1級(jí)回文串