题目大意:给定一个字符串求咜所有长度为奇数的回文子串中,前k小的长度乘积.若数量超过k输出-1.
一看就是道manacher裸题由于长度要求为奇数,所以就不需要在字符串中间插叺奇奇怪怪的字符啦只需要在两边插入不一样的字符就可以了.
我们再设一个数组cnt[i]表示长度为i的回文子串有多少个,那么每得到一个新的朂长回文子串长度pal[i]我们就可以将1~pal[i]的所有cnt值都加1但是这样太慢了所以我们差分一下.
最后我们从1开始枚举,每次加2.当枚举到i时得到的贡献为icnt[i]快速幂搞一下就可以了.