Solution $ans=$回文子序列$-$回文子串的数目。 后者可以用$manacher$直接求。 前者设$f[i]$表示以$i$为中心的对称的字母对数。 那么回文子序列的数量也就是$\sum_{i=0}^{n-1}2^{f[i]-1}$ 构造两个数组$a[i],b[i]$。若第$i$位为$a$，那么$a[i]=1$，否则$b[i]=1$。 可以发现$a$数组自身卷积就是$a$字

Description Input Solution 考虑先忽略不可以连成一段的条件。 那么，暴力的做法就是，枚举一个中心点，暴力找出旁边有多少个对称的点，设数量为\(x\)，则这个中心点对答案的贡献为\(2^x-1\)。 这样是\(O(n^2)\)的，考虑怎么优化。 对于中心点\(mid\)，能对\(x\)造成贡献的位置\(i,j\)，一定是满足\(i+j=mid*2\)且\(s[i]=

【bzoj3160】万径人踪灭 FFT 题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3160 我是一个傻叉 微笑脸 1 #include<bits/stdc++.h> 2 #define inf 1000000000 3 #define ll long long 4 #define N 200005 5 #de

。。恩 打了四五遍 不会也背出来了。。 BZOJ3160 【听说时限紧？转C++的优势么？】 上AC代码 fft 1 /*Problem: 3160 2 User: cyz666 3 Language: C++ 4 Result: Accepted 5 Time:1992 ms 6 Memory:18492 kb 7 ********