[bzoj 3160] 万径人踪灭

在一个长度为n只含'a','b'的字符串中选取一个子序列, 使得: 1. 位置和字符都关于某条对称轴对称. 2. 不是连续的一段.

求方案数对(10^9+7)取模的结果. (n≤10^5) > 来山上玩的人, 也不全是来欣赏山上的风景的.

vfk的语文水平和摄影技术都很高 QAQ

先不考虑限制2. 求出满足限制1的序列数目, 跑一遍Manacher, 减掉这些.

一开始想把原串和它的转置做匹配, 然后发觉不如直接思考.

从0开始标号. 枚举对称轴, 关于它对称且满足限制1的子序列个数:

字符只有两种, 可以枚举再相加:

这是一个卷积, FFT求之.

typedef complex<double> Complex;
typedef long long ll;
const double pi = acos(-1);
const int N = 1e5, M = 1e9 + 7, L = (1<<18) + 1;

namespace Convol {
	int n, rev[L];
	
	void init(int _n, int s)
	{
		n = _n;
		--s;
		rep (i, 0, n)
			rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << s);
	}

	void fft(Complex a[], int d=1)
	{
		rep (i, 0, n)
			if (rev[i] < i)
				swap(a[rev[i]], a[i]);
		for (int m = 1; m < n; m <<= 1) {
			Complex _w(cos(pi/m), d*sin(pi/m));
			for (int j = 0; j < n; j += m<<1) {
				Complex w(1);
				rep (k, 0, m) {
					Complex t = w * a[j+m+k];
					a[j+m+k] = a[j+k] - t;
					a[j+k] += t;
					w *= _w;
				}
			}
		}
		if (d == -1)
			rep (i, 0, n) a[i] /= n;
	}

	void convol(Complex a[], Complex b[])
	{
		fft(a);
		rep (i, 0, n) {
			int j = (n-i) & (n-1);
			b[i] = Complex(0, 0.25) * (conj(a[j] * a[j]) - a[i] * a[i]);
		}
		fft(b, -1);
	}
}

using Convol::convol;

int f[2*N + 1];
char s[N + 1];

void manacher(int n)
{
	static char t[2*N + 1];
	rep (i, 0, n) {
		t[i*2] = '#';
		t[i*2+1] = s[i];
	}
	t[2*n] = '#';
	int mx = -1, j = -1;
	rep (i, 0, 2*n+1) {
		f[i] = i < mx ? min(mx-i, f[2*j-i]) + 1 : 1;
		while (f[i] <= i && i+f[i] <= 2*n && t[i+f[i]] == t[i-f[i]]) ++f[i];
		if (i + --f[i] > mx) {
			mx = i + f[i];
			j = i;
		}
	}
}

Complex x[L], y[L];
int cnt[2*N], pow2[N + 1];

int main()
{
	scanf("%s", s);
	int n = strlen(s), m = 1, p = 0;
	while (m < 2*n-1) m <<= 1, ++p;
	Convol::init(m, p);
	
	rep (i, 0, n)
		x[i] = s[i] == 'a' ? Complex(1, 1) : 0;
	convol(x, y);
	rep (i, 0, 2*n)
		cnt[i] = round(real(y[i]));
	
	rep (i, 0, n)
		x[i] = s[i] == 'b' ? Complex(1, 1) : 0;
	rep (i, n, m)
		x[i] = 0;
	convol(x, y);
	rep (i, 0, 2*n)
		cnt[i] += round(real(y[i]));

	pow2[0] = 1;
	rep (i, 1, n+1) pow2[i] = pow2[i-1] * 2 % M;

	ll ans = 0;
	rep (i, 0, 2*n)
		(ans += pow2[(cnt[i]+1)/2] + M - 1) %= M;

	manacher(n);
	rep (i, 0, 2*n + 1)
		(ans += M - (f[i]+1)/2) %= M;

	printf("%lld\n", ans);
	
	return 0;
}