万径人踪灭 bzoj-3160
题目大意：给定一个ab串。求所有的子序列满足：位置和字符都关于某条对称轴对称而且不连续。
注释：$1le nle 10^5$。
想法：
看了大爷的题解，OrzOrz。
因为对称轴可以是两个字符中间的位置，所以我们把字符串按照$Manacher$的形式倍增。
我们希望处理出一个数组$f$，$f_i$表示以$i$为对称轴的左右相等字符个数。
以当前位置为对称轴的答案显然就是$2^{f_i}-1$。
因为还有不连续的条件，我们只需要减掉$Manacher$的回文半径即可。
现在考虑如何能求出$f$数组。
不难发现：其实原序列中的第$i$个字符如果和第$j$个字符相等那么会更新到倍增序列后的第$i+j$个字符。
所以$f_i=((sumlimits_{j=0}^{i-1} (s[j]==s[i-j]))+1)/2$。
看起来像卷积的形式，想到$FFT$。
但是$FFT$只能做乘法，这个题怎么办？
我们先把所有的$a$字符都变成$1$，$b$字符变成$0$，然后统计$((sumlimits_{j=0}^{i-1} a[j]cdot a[i-j])+1)/2$。
再把所有的$b$字符变成$1$，$a$字符变成$0$。
用$FFT$优化卷积即可。
Code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define mod 1000000007
#define N 100010
using namespace std;
typedef long long ll;
typedef double db;
const db pi=acos(-1);
struct cp
{
db x,y;
cp() {x=y=0;}
cp(db x_,db y_){x=x_,y=y_;}
cp operator + (const cp &a) const {return cp(x+a.x,y+a.y);}
cp operator - (const cp &a) const {return cp(x-a.x,y-a.y);}
cp operator * (const cp &a) const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}
}a[N<<2];
void fft(cp *a,int len,int flg)
{
int i,j,k,t;
cp w,wn,tmp;
for(i=k=0;i<len;i++)
{
if(i>k) swap(a[i],a[k]);
for(j=len>>1;(k^=j)<j;j>>=1);
}
for(k=2;k<=len;k<<=1)
{
t=k>>1;
wn=cp(cos(2*pi*flg/k),sin(2*pi*flg/k));
for(i=0;i<len;i+=k)
{
w=cp(1,0);
for(j=i;j<i+t;j++)
{
tmp=a[j+t]*w;
a[j+t]=a[j]-tmp;
a[j]=a[j]+tmp;
w=w*wn;
}
}
}
if(flg==-1) for(i=0;i<len;i++) a[i].x/=len;
}
char s[N],t[N<<1];int f[N<<1],n,m,c[N<<2],ans,p[N<<2];
void manacher()
{
for(int i=0;i<n;i++)
{
t[++m]='#';
t[++m]=s[i];
}
t[++m]='#';
f[1]=0;
for(int now=1,i=1;i<=m;i++)
{
f[i]=min(f[(now<<1)-i],now+f[now]-i);
for(;i+f[i]<m&&i-f[i]>1;f[i]++) if(t[i+f[i]+1]!=t[i-f[i]-1]) break;
if(i+f[i]>now+f[now]) now=i;
ans-=(f[i]+1)>>1;
ans%=mod;
}
}
int main()
{
scanf("%s",s); n=strlen(s);
int len=1; while(len<(n<<1))len<<=1;
for(int i=0;i<n;i++) a[i].x=(s[i]=='a');
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++) c[i]=(int)(a[i].x+0.1),a[i]=cp();
for(int i=0;i<n;i++) a[i].x=(s[i]=='b');
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++) c[i]+=(int)(a[i].x+0.1);
manacher();
p[0]=1;
for(int i=1;i<len;i++) p[i]=(p[i-1]<<1)%mod;
for(int i=0;i<len;i++) ans=(ans+p[(c[i]+1)>>1]-1)%mod;
printf("%d
",(ans+mod)%mod);
return 0;
}
小结：好题好题。比那个什么孤舟蓑笠翁友善多了。
这个题主要是需要想到求$f$数组。而且连续的话需要用$Manacher$减掉，非常好的一道题。