Record

思路大概是：

假定 $a_i=0(i\ge n)$。

令：$t0=2i,t1=2i+1\\$。

设：

• $f_i$ ：以 $i$ 为对称中心，两边最多能匹配的对数（包括自己）；
• 而 $g$ 是枚举分割线。

则有

$$\begin{aligned}\{a,b\}&\to \{-1,1\}\\f_i&=\sum_{j=0}^{\min(i,n-i-1)}\dfrac{a[i-j]\times a[i+j]+1}{2}\\&=\dfrac14\left(\left(\sum_{j=0}^{t0}a[t0-j]\times a[j]\right)+(a[i]\times a[i] + 1) + \min(t0, n-1) - \max(0, t0-n+1) + 1\right)\\g_i&=\sum_{j=1}^{\min(i,n-i)}\dfrac{a[i-j]\times a[i+j-1]+1}{2}\\&=\dfrac14\left(\left(\sum_{j=0}^{t1}a[t1-j]\times a[j]\right)+ \min(t1 n-1) - \max(0, t0-n+1) + 1\right)\\\end{aligned}$$

然后答案就是：

$$Ans=\sum_{i=0}^{n-1}(2^{f[i]}-1)+\sum_{i=1}^{n-1}(2^{g[i]}-1)-res$$

其中 $res$ 为字符串中回文串个数，这个可以用 Manacher 算。

$f,g$ 卷积算完之后加上后面的那部分即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int N = (1<<18)+5, mod = 998244353, gen = 3, mod2 = 1e9 + 7;
char s[N];
int a[N], n, f[N], g[N], p[N], lim, len, r[N], b[N], _a[N];
int qpow (long long a, int b) {
	long long res = 1;
	for (; b; b >>= 1, (a *= a) %= mod)
		if (b & 1) (res *= a) %= mod;
	return res;
}
int qpow2 (long long a, int b) {
	long long res = 1;
	for (; b; b >>= 1, (a *= a) %= mod2)
		if (b & 1) (res *= a) %= mod2;
	return res;
}
int Manacher (char *_s, int n) {
	static char s[N<<1];
	for (int i = 1; i <= n; i++) s[i<<1] = _s[i-1], s[i<<1|1] = '#';
	s[1] = '#', n = n<<1|1, s[0] = '$', s[n+1] = '@';
	static int j, R;
	for (int i = 1; i <= n; i++) {
		int &x = p[i];
		x = i <= R ? min(p[(j*2)-i], R-i) : 0;
		while (s[i-x-1] == s[i+x+1]) x++;
		if (i+p[i] > R) j = i, R = i+p[i];
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) (ans += i & 1 ? p[i]/2 : (p[i]+1)/2) %= mod;
	return ans;
}
void ntt (int *f, int n, int sign) {
	for (int i = 0; i < n; i++)
		if (i < r[i]) swap(f[i], f[r[i]]);
	for (int mid = 1; mid < n; mid<<=1) {
		int o = qpow(gen, 1ll*sign*(mod-1)/(mid<<1)%(mod-1)+(mod-1));
		for (int i = 0, w; i < n; i += mid<<1) {
			w = 1;
			for (int j = 0; j < mid; j++, w = 1ll*w*o%mod) {
				int x = f[i+j], y = 1ll*w*f[i+mid+j]%mod;
				f[i+j] = (1ll*x+y) % mod;
				f[i+mid+j] = (1ll*x-y+mod) % mod;
			}
		}
	}
	if (sign == -1) {
		int inv = qpow(n, mod-2);
		for (int i = 0; i < n; i++) f[i] = 1ll*f[i]*inv%mod;
	}
}
signed main () {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> s, n = strlen(s);
	for (int i = 0; i < n; i++) _a[i] = a[i] = s[i] == 'a' ? 1 : mod-1;
	for (lim=1, len=0; lim <= n+n; lim<<=1, len++);
	for (int i = 0; i <= lim; i++)
		r[i] = (r[i>>1]>>1)|((i&1)<<(len-1));
	cerr << lim << '\n';
	ntt(_a, lim, 1);
	for (int i = 0; i <= lim; i++) b[i] = 1ll*_a[i] * _a[i] % mod;
	ntt(b, lim, -1);
	int inv4 = qpow(4, mod-2);
	for (int i = 0; i < n; i++) {
		int t = i*2;
		f[i] = (1ll*b[t] + a[i] * a[i] + 1 + min(t, n-1) - max(0ll, t-n+1) + 1) % mod * inv4 % mod;
	}
	for (int i = 1; i < n; i++) {
		int t = i*2-1;
		g[i] = (1ll*b[t] + min(t, n-1) - max(0ll, t-n+1) + 1) % mod * inv4 % mod;
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) (ans += qpow2(2, f[i]) - 1) %= mod2;
	for (int i = 1; i < n; i++) (ans += qpow2(2, g[i]) - 1) %= mod2;
	cout << (ans - Manacher(s, n) + mod2) % mod2;
	return 0;
}