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

题意：

一个字符是 1 级回文。一个字符串是 k 级回文当且仅当下面条件成立：

1. 它的左边一半与右边一半对称，如果字符串长度为7，则一半长度为3；

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

左半字符串 t 的前缀长度为 ⌊t|2⌋，右半字符串是同样长度的后缀。⌊t|2⌋ 是字符串 t 的长度除以 2 以后向下取整。

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

如果一个回文子串出现多次，则也被计数多次。

题解：

使用区间 dp 进行计算。设 dp[L][r] 表示区间 [L,r] 是几级回文串。

如果不是回文串则值为 0。先预处理出 dp[i][i] 的值。之后，转移方程为：

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 数组先记录每级回文串有多少个，然后再加上所有大于当前回文串级数的回文串个数。

例如：2级回文串 也是 1级回文串