# [bzoj] 31.6 million tracks mancher + FFT

## 3160: Wanjing

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

## Description  ## Input ## HINT ## Source

2013 Hubei mutual measurement week1

[Submit][Status][Discuss] ﻿

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 = '+', 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 = 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;
}```

Added by montana111 on Thu, 30 Apr 2020 16:57:25 +0300