3160: Wanjing

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1753  Solved: 977
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

Source

[Submit][Status][Discuss] 

HOME Back

The first practice after FFT board ~ this problem requires to find discontinuous palindrome subsequence (position symmetry), which looks very bad, right or wrong ~ so we should consider complement transformation. This is equal to all palindrome subsequence - continuous palindrome subsequence. The latter one can be done directly by Manacher. We should consider how to do the former one

We make f[i] be the logarithm of symmetry and equality about position I in array s after the supplement of manacher. Then if x, y want to satisfy this condition to be a pair, we will find that this requires the original string (x / 2) + (y / 2) = i, because X / 2 and y / 2 are actually the original string position + 1(x, y is in s). So if ss[x] in the original string is equal to ss[y], then it is symmetrical about the position of x + 1 + y + 1 in S. then there are:

fi=⌊1+∑i−2j=0[sj==si−2−j]2   ⌋

It turns out that it's a convolution, so you can enjoy FFT. In the beginning, Manacher wrote the wrong T, and he lost his reputation

#include<bits/stdc++.h>
using namespace std;
typedef long long lnt;
typedef complex<double> C;
const int mod = 1e9 + 7;
const int maxn = 4e5 + 5;
const double pi = acos(-1.0);
lnt ans;
char ss[maxn], s[maxn];
int n, L, rev[maxn], pal[maxn], pw[maxn], f[maxn];
C a[maxn], b[maxn];
inline void FFT(C *a, int f) {
	C x, y;
	for (int i = 0; i < n; ++ i)
		if (rev[i] > i) swap(a[i], a[rev[i]]);
	for (int i = 1; i < n; i <<= 1) {
		C wn(cos(pi / i), f * sin(pi / i));
		for (int j = 0; j < n; j += i << 1) {
			C w = 1;
			for (int k = 0; k < i; ++ k, w *= wn) {
				x = a[j + k], y = w * a[j + k + i];
				a[j + k] = x + y, a[j + k + i] = x - y;
			}
		}
	}
}
inline int manacher(char *r) {
	int m = 0, mx = 0, id = 0, sum = 0;
	for (int i = 0; r[i]; ++ i) s[++ m] = '#', s[++ m] = r[i];
	s[0] = '+', s[++ m] = '#';
	for (int i = 1; i < m; ++ i) {
		if (mx > i) pal[i] = min(mx - i, pal[2 * id - i]);
		while (s[i - pal[i]] == s[i + pal[i]]) pal[i] ++;
		if (i + pal[i] > mx) mx = pal[i] + i, id = i;
		sum = sum + pal[i] / 2;
		if (sum > mod) sum -= mod;
	}
	return sum;
}
int main() {
	scanf("%s", ss);
	int len = strlen(ss);
	register int i;
	for (pw[0] = 1, i = 1; i < maxn; ++ i) pw[i] = (pw[i - 1] << 1) % mod;
	for (n = 1; n <= len << 1; n <<= 1) L ++;
	for (i = 0; i < n; ++ i) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (L - 1));
	for (i = 0; i < n; ++ i) a[i] = (ss[i] == 'a');
	FFT(a, 1);
	for (i = 0; i < n; ++ i) b[i] += a[i] * a[i];
	for (i = 0; i < n; ++ i) a[i] = (ss[i] == 'b');
	FFT(a, 1);
	for (i = 0; i < n; ++ i) b[i] += a[i] * a[i];
	FFT(b, -1);
	for (i = 2; i <= len << 1; ++ i) f[i] += (lnt)(b[i - 2].real() + 0.5) / n;
	for (i = 2; i <= len << 1; ++ i) ans = (ans + pw[(f[i] + 1) >> 1] - 1) % mod;
	printf("%lld\n", (ans - manacher(ss) + mod) % mod);
	return 0;
}