[bzoj3160]万径人踪灭_FFT_Manacher

时间：2023-03-10 08:15:25
[bzoj3160]万径人踪灭_FFT_Manacher

万径人踪灭 bzoj-3160

题目大意：给定一个ab串。求所有的子序列满足：位置和字符都关于某条对称轴对称而且不连续。

注释：$1\le n\le 10^5$。

想法：

看了大爷的题解，OrzOrz。

因为对称轴可以是两个字符中间的位置，所以我们把字符串按照$Manacher$的形式倍增。

我们希望处理出一个数组$f$，$f_i$表示以$i$为对称轴的左右相等字符个数。

以当前位置为对称轴的答案显然就是$2^{f_i}-1$。

因为还有不连续的条件，我们只需要减掉$Manacher$的回文半径即可。

现在考虑如何能求出$f$数组。

不难发现：其实原序列中的第$i$个字符如果和第$j$个字符相等那么会更新到倍增序列后的第$i+j$个字符。

所以$f_i=((\sum\limits_{j=0}^{i-1} (s[j]==s[i-j]))+1)/2$。

看起来像卷积的形式，想到$FFT$。

但是$FFT$只能做乘法，这个题怎么办？

我们先把所有的$a$字符都变成$1$，$b$字符变成$0$，然后统计$((\sum\limits_{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\n",(ans+mod)%mod);

	return 0;

}

小结：好题好题。比那个什么孤舟蓑笠翁友善多了。

　　这个题主要是需要想到求$f$数组。而且连续的话需要用$Manacher$减掉，非常好的一道题。

相关文章