BZOJ 3160: 万径人踪灭（FFT+manacher）

Posted On 2019年2月20日

3160: 万径人踪灭

友情提示：真·题面只有3行

Solution

显然可以对于$a$与$b$分别构造多项式，以$\frac{i}{2}$为对称轴的可行块数：$aw[i]=\sum_{a,b} \sum_{j=0}^{i}a[j]\cdot a[i-j]$

则答案为（注意是2的幂）

再用manacher求出连续的回文串减去以对应位置为对称轴的回文串的贡献即可

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
struct cpx{double r,i;cpx(){};cpx(const double&_r,const double&_i){r=_r;i=_i;};};
cpx operator + (const cpx&a,const cpx&b){return cpx(a.r+b.r,a.i+b.i);}
cpx operator - (const cpx&a,const cpx&b){return cpx(a.r-b.r,a.i-b.i);}
cpx operator * (const cpx&a,const cpx&b){return cpx(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}
inline int read()
{
	int f=1,k=0;char c=getchar();
	while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
	return k*f;
}
inline int min(const int a,const int b){return a<b?a:b;}
inline int ABS(const int x){return x<0?-x:x;}
const int maxn=100105<<3,P=1e9+7;
const double pi=acos(-1);
int R[maxn],n,m,L,sigma[maxn],ans;
char s[maxn],no,t[maxn];
cpx a[maxn],empty;
inline void dec(int&x,const int delta){x-=delta;if (x<0)x+=P;if (x>=P)x-=P;}
inline void inc(int&x,const int delta){x+=delta;if (x<0)x+=P;if (x>=P)x-=P;}
inline void FFT(cpx*a,int f)
{
	for (int i=0;i<n;i++)if (i<R[i])swap(a[i],a[R[i]]);
	for (int i=1;i<n;i<<=1)
	{
		cpx wn(cos(pi/i),f*sin(pi/i));
		for (int j=0;j<n;j+=(i<<1))
		{
			cpx w(1,0);
			for (int k=0;k<i;k++,w=w*wn)
			{
				cpx x=a[j+k],y=w*a[j+k+i];
				a[j+k]=x+y;
				a[j+k+i]=x-y;
			}
		}
	}
	if (f==-1)for (int i=0;i<n;i++)a[i].r/=n,a[i].i=0;
}
int flr(double x)
{
	return x+1e-3;
}
int sswr(double x)
{
	return x+0.51;
}
int h[maxn];
inline void work(char*t)
{
	t[0]='#';t[n*2+2+1]='$';t[n*2+2+2]='\0';
	for (int i=0;i<=n;i++)t[(i<<1)+1]=s[i],t[(i<<1)+2]='#';
	int len=strlen(s)<<1,mxr=0,mid=0;--len;
	for (int i=1;i<=len;i++)
	{
		if (i>=mxr)h[i]=1;
		else h[i]=min(h[mid*2-i],h[mid]+mid-i);
		for (;t[i-h[i]]==t[i+h[i]];++h[i]);
		if (mxr<h[i]+i)mxr=h[i]+i,mid=i;
		dec(ans,(h[i])>>1);
	}
}
int mi[maxn];
signed main()
{
	scanf("%s",s);
	int len=strlen(s);
	mi[0]=1;
	for (int i=1;i<=len+1;i++)(mi[i]=mi[i-1]*2)>=P&&(mi[i]-=P);
	n=strlen(s)-1;
	for (int i=0;i<=n;i++)a[i].r=s[i]=='a';
	m=n<<1;
	for (n=1;n<=m;n<<=1)L++;
	for (int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	FFT(a,1);
	for (int i=0;i<=n;i++)a[i]=a[i]*a[i];
	FFT(a,-1);
	for (int i=0;i<=m;i++)sigma[i]=flr(a[i].r);
	for (int i=0;i<=m;i++)a[i]=empty;
	for (int i=0;i<=n;i++)a[i].r=s[i]=='b';
	FFT(a,1);
	for (int i=0;i<=n;i++)a[i]=a[i]*a[i];
	FFT(a,-1);
	for (int i=0;i<=m;i++)sigma[i]+=flr(a[i].r);
	for (int i=0;i<=m;i++)
		inc(ans,mi[sswr(1.0*sigma[i]/2)]-1);
	t[0]='@';
	work(t+1);
	printf("%d\n",ans);
}

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

using namespace std;

struct cpx{double r,i;cpx(){};cpx(const double&_r,const double&_i){r=_r;i=_i;};};

cpx operator + (const cpx&a,const cpx&b){return cpx(a.r+b.r,a.i+b.i);}

cpx operator - (const cpx&a,const cpx&b){return cpx(a.r-b.r,a.i-b.i);}

cpx operator * (const cpx&a,const cpx&b){return cpx(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}

inline int read()

{

int f=1,k=0;char c=getchar();

while (c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();

while (c>='0'&&c<='9')k=k*10+c-'0',c=getchar();

return k*f;

}

inline int min(const int a,const int b){return a<b?a:b;}

inline int ABS(const int x){return x<0?-x:x;}

const int maxn=100105<<3,P=1e9+7;

const double pi=acos(-1);

int R[maxn],n,m,L,sigma[maxn],ans;

char s[maxn],no,t[maxn];

cpx a[maxn],empty;

inline void dec(int&x,const int delta){x-=delta;if (x<0)x+=P;if (x>=P)x-=P;}

inline void inc(int&x,const int delta){x+=delta;if (x<0)x+=P;if (x>=P)x-=P;}

inline void FFT(cpx*a,int f)

{

for (int i=0;i<n;i++)if (i<R[i])swap(a[i],a[R[i]]);

for (int i=1;i<n;i<<=1)

{

cpx wn(cos(pi/i),f*sin(pi/i));

for (int j=0;j<n;j+=(i<<1))

{

cpx w(1,0);

for (int k=0;k<i;k++,w=w*wn)

{

cpx x=a[j+k],y=w*a[j+k+i];

a[j+k]=x+y;

a[j+k+i]=x-y;

}

if (f==-1)for (int i=0;i<n;i++)a[i].r/=n,a[i].i=0;

}

int flr(double x)

{

return x+1e-3;

}

int sswr(double x)

{

return x+0.51;

}

int h[maxn];

inline void work(char*t)

{

t[0]='#';t[n*2+2+1]='$';t[n*2+2+2]='\0';

for (int i=0;i<=n;i++)t[(i<<1)+1]=s[i],t[(i<<1)+2]='#';

int len=strlen(s)<<1,mxr=0,mid=0;--len;

for (int i=1;i<=len;i++)

{

if (i>=mxr)h[i]=1;

else h[i]=min(h[mid*2-i],h[mid]+mid-i);

for (;t[i-h[i]]==t[i+h[i]];++h[i]);

if (mxr<h[i]+i)mxr=h[i]+i,mid=i;

dec(ans,(h[i])>>1);

}

int mi[maxn];

signed main()

{

scanf("%s",s);

int len=strlen(s);

mi[0]=1;

for (int i=1;i<=len+1;i++)(mi[i]=mi[i-1]*2)>=P&&(mi[i]-=P);

n=strlen(s)-1;

for (int i=0;i<=n;i++)a[i].r=s[i]=='a';

m=n<<1;

for (n=1;n<=m;n<<=1)L++;

for (int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));

FFT(a,1);

for (int i=0;i<=n;i++)a[i]=a[i]*a[i];

FFT(a,-1);

for (int i=0;i<=m;i++)sigma[i]=flr(a[i].r);

for (int i=0;i<=m;i++)a[i]=empty;

for (int i=0;i<=n;i++)a[i].r=s[i]=='b';

FFT(a,1);

for (int i=0;i<=n;i++)a[i]=a[i]*a[i];

FFT(a,-1);

for (int i=0;i<=m;i++)sigma[i]+=flr(a[i].r);

for (int i=0;i<=m;i++)

inc(ans,mi[sswr(1.0*sigma[i]/2)]-1);

t[0]='@';

work(t+1);

printf("%d\n",ans);

}

0 0 vote

Article Rating

0 评论

Inline Feedbacks

View all comments