考虑容斥：拿满足条件 \(1\) 的方案数减去满足条件 \(1\) 但不满足条件 \(2\) 的方案数就是答案。
满足条件 \(1\) 但不满足条件 \(2\) 的方案可以用 \(\text{Manacher}\) 算法 \(O(n)\) 计算。
对于满足条件 \(1\) 的总方案数，我们记 \(c_i\) 表示以 \(i\) 位置为对称轴时，满足条件的位置对的数量（即两个位置上的字符相同，且 \(i\) 位置是它们的对称轴），那么显而易见，答案就是 \(\sum (2^{f_i}-1)\)。
所以现在的问题就是 \(c_i\) 怎么求。我们枚举每一种字符并设其为 \(ch\)，之后将序列中对应位置字符为 \(ch\) 的位置标为 \(1\)，将新数列与其翻转后的数列加法卷积一下就可以得到只考虑某种字符的 \(c'\) 数组。而最终的 \(c\) 数组也就是各个 \(c'\) 数组的加和。
点击查看代码
#include <bits/stdc++.h>
namespace Poly{
constexpr int N = 2.7e5 + 10;
constexpr double Pi = acos(-1);
int n, m, p[N];
std::complex<double> f[N], g[N];
void FFT(int n, std::complex<double> *c, int x = 1){
for(int i = 0; i < n; ++i) if(i < p[i]) std::swap(c[i], c[p[i]]);
for(int b = 2, k = 1; b <= n; b <<= 1, k <<= 1){
std::complex<double> t(cos(2 * Pi / b), sin(2 * Pi / b) * x), w(1, 0);
for(int i = 0; i < n; i += b, w = 1){
for(int j = 0; j < k; ++j, w *= t){
c[i + j] += c[i + j + k] * w;
c[i + j + k] = c[i + j] - c[i + j + k] * w - c[i + j + k] * w;
}
}
}
}
std::vector<double> Convolution(const auto &a, const auto &b){
if(!a.size() || !b.size()) return std::vector<double>();
n = a.size(), m = b.size();
int l = 1 << (int)ceil(log2(n + m - 1));
for(int i = 0; i < l; ++i){
f[i] = i < n? a[i] : 0, g[i] = i < m? b[i] : 0;
p[i] = (p[i >> 1] >> 1) | (i & 1? l >> 1 : 0);
}
n += m - 1, FFT(l, f), FFT(l, g);
for(int i = 0; i < l; ++i) f[i] *= g[i];
FFT(l, f, -1); std::vector<double> ret;
for(int i = 0; i < n; ++i)
ret.emplace_back(f[i].real() / l);
return ret;
}
}
namespace String{
constexpr int N = 1e5 + 10;
char s[N << 1]; int n, p[N << 1];
long long Manacher(char a[]){
int la = strlen(a);
s[n = 0] = '$', s[++n] = '#';
for(int i = 0; i < la; ++i) s[++n] = a[i], s[++n] = '#';
s[n + 1] = '%';
int m = 0, r = 0; long long ans = 0;
for(int i = 1; i <= n; ++i){
p[i] = (i <= r? std::min(p[m * 2 - i], r - i + 1) : 1);
while(s[i - p[i]] == s[i + p[i]]) ++p[i];
if(i + p[i] - 1 > r) m = i, r = i + p[i] - 1;
ans += (p[i] >> 1);
}
return ans;
}
}
#define FL(i, a, b) for(int i = (a); i <= (b); ++i)
#define FR(i, a, b) for(int i = (a); i >= (b); --i)
using Poly::Convolution;
using String::Manacher;
constexpr int N = 1e5 + 10, p = 1e9 + 7;
int n, m, pw[N], a[N << 1], ans;
char str[N]; std::vector<int> v;
int main(){
scanf("%s", str);
n = strlen(str), pw[0] = 1;
FL(i, 1, n) pw[i] = (pw[i - 1] << 1) % p;
auto C = [](int x){
v.resize(n);
FL(i, 0, n - 1) v[i] = (str[i] - 'a') ^ x;
auto t = Convolution(v, v);
FL(i, 0, (n - 1) * 2) a[i] += (int)round(t[i]);
};
C(0), C(1);
FL(i, 0, (n - 1) * 2){
ans = (ans + pw[(a[i] + 1) >> 1] - 1) % p;
}
printf("%lld\n", ((ans - Manacher(str)) % p + p) % p);
return 0;
}