Description：

求一个 $01$ 串不连续回文子序列个数。

$1\leqslant n\leqslant 10^5$

Solution：

不连续回文子序列个数 $=$ 回文子序列个数 $-$ 回文子串个数。

后面那个可以用 $manacher$ 求，重点在前面。

我们知道字符串匹配除了经典的字符串算法还有一个东西叫 $FFT$ ，对于这道题，没有什么数据结构可以用，那考虑推一下答案的式子，会发现就是每个位置两边有多少个相同的对，像 $manacher$ 那样把所有的都补成奇回文串： $$ ans=\sum_{p=1}^l(2^{\begin{align}\sum_{i=1}^k[a[p-i]=a[p+i]]\ne'\#'\end{align}}-1) $$ 然后发现上面那个式子就是把原来 $01$ 串当作多项式自乘一下得到的，这样统计就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 800010

char str[MAXN],s[MAXN];

int n = 0;

int h[MAXN];

const double PI = acos(-1);

int cnt[MAXN];

int power[MAXN];

struct comp

{

	double r,i;

}a[MAXN];

comp operator + (comp a,comp b){return (comp){a.r + b.r,a.i + b.i};}

comp operator - (comp a,comp b){return (comp){a.r - b.r,a.i - b.i};}

comp operator * (comp a,comp b){return (comp){a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r};}

int rev[MAXN];

void FFT(comp f[],int l,int type)

{

	for(int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(int i = 2;i <= l;i = i << 1)

	{

		comp wn = (comp){cos(-type * 2 * PI / i),sin(-type * 2 * PI / i)};

		for(int j = 0;j < l;j += i)

		{

			comp w = (comp){1,0};

			for(int k = j;k < j + i / 2;++k)

			{

				comp u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}//cout << "(((" << endl;

	if(type == -1)

	{

		for(int i = 0;i < l;++i)f[i].r /= l;

	}

	return;

}

#define MOD 1000000007

int main()

{

	scanf("%s",str + 1);

	int l = strlen(str + 1);

	s[++n] = '#';

	for(int i = 1;i <= l;++i)

	{

		s[++n] = str[i];

		s[++n] = '#';

	}

	int maxr = 1,pos = 1;

	for(int i = 1;i <= n;++i)

	{

		if(maxr >= i)h[i] = min(maxr - i + 1,h[2 * pos - i]);

		else h[i] = 1;

		while(i + h[i] <= n && i - h[i] >= 1 && s[i + h[i]] == s[i - h[i]])++h[i];

		if(i + h[i] - 1 >= maxr){maxr = i + h[i] - 1;pos = i;}

	}

	int ln = 0,len = 1;

	for(;len <= 2 * l;len = len << 1,++ln);

	for(int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (ln - 1));

	for(int i = 1;i <= l;++i)a[i - 1].r = (str[i] == 'a' ? 1 : 0);

	FFT(a,len,1);

	for(int i = 0;i < len;++i)a[i] = a[i] * a[i];

	FFT(a,len,-1);

	for(int i = 0;i < len;++i)cnt[i] += (int(a[i].r + 0.5) + 1) / 2;

	memset(a,0,sizeof(a));

	for(int i = 1;i <= l;++i)a[i - 1].r = (str[i] == 'b' ? 1 : 0);

	FFT(a,len,1);

	for(int i = 0;i < len;++i)a[i] = a[i] * a[i];

	FFT(a,len,-1);

	for(int i = 0;i < len;++i)cnt[i] += (int(a[i].r + 0.5) + 1) / 2;

	int ans = 0;

	power[0] = 1;

	for(int i = 1;i <= n;++i)power[i] = power[i - 1] * 2 % MOD;

	for(int i = 0;i < len;++i)ans = (ans + power[cnt[i]] - 1) % MOD;

	for(int i = 1;i <= n;++i)ans = (ans - h[i] / 2 + MOD) % MOD;

	cout << ans << endl;

	return 0;

}