bzoj 3160: 万径人踪灭 manachar + FFT

3160: 万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 133  Solved: 80
[Submit][Status][Discuss]

Description

bzoj 3160: 万径人踪灭 manachar + FFT

bzoj 3160: 万径人踪灭 manachar + FFT

Input

bzoj 3160: 万径人踪灭 manachar + FFT

Output

 

Sample Input

 

Sample Output

 

HINT

bzoj 3160: 万径人踪灭 manachar + FFT

  以每一个位置为中心,分别处理连续一块的回文串,回文序列个数。

  比较容易看出是FFT+manachar,但是FFT还是不太熟悉,特别要注意三层for语句中i,j,k不能写错,这东西很难调试出来。

  另外一点就是manachar加‘#’最好头尾都加,要不然第一个,最后一个字符回文串长度会出问题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 610000
#define MOD 1000000007
typedef long long qword;
typedef double real;
const real pi=acos(-);
struct Complex
{
real x,y;
Complex(real x,real y=):x(x),y(y){}
Complex(){}
};
Complex operator +(Complex c1,Complex c2)
{
return Complex(c1.x+c2.x,c1.y+c2.y);
}
Complex operator -(Complex c1,Complex c2)
{
return Complex(c1.x-c2.x,c1.y-c2.y);
}
Complex operator *(Complex c1,Complex c2)
{
return Complex(c1.x*c2.x-c1.y*c2.y,c1.x*c2.y+c1.y*c2.x);
}
Complex operator /(Complex c1,real x)
{
return Complex(c1.x/x,c1.y/x);
}
Complex g1[MAXN],g2[MAXN],g3[MAXN];
Complex gt[MAXN];
void FFT(Complex gg[],int l,int pp)
{
memcpy(gt,gg,sizeof(gt[])*l);
int x;
for (int i=;i<l;i++)
{
x=;
for (int j=,k=l>>;j<l;j<<=,k>>=)
if (i&j)x+=k;
gg[i]=gt[x];
}
Complex w;
Complex wn;
Complex tmp;
for (int i=;i<l;i<<=)
{
wn=Complex(cos(pi/i*pp),sin(pi/i*pp));
for (int j=;j<l;j+=(i<<))
{
w=Complex(,);
for (int k=;k<i;k++)
{
tmp=gg[j+k];
gg[j+k]=gg[j+k]+gg[i+j+k]*w;
gg[i+j+k]=tmp-w*gg[i+j+k];
w=w*wn;
}
}
}
}
qword pow_mod(qword x,qword y)
{
qword ret=;
while (y)
{
if (y&)ret=ret*x%MOD;
x=x*x%MOD;
y>>=;
}
return ret;
}
char str[MAXN];
char str2[MAXN];
int plen[MAXN];
int plen2[MAXN];
void manachar(int l)
{
int id=-,mx=;
for (int i=;i<l;i++)
{
if (mx>i)
plen[i]=min(mx-i,plen[id*-i]);
while (i-plen[i]->= && i+plen[i]+<l && str2[i-plen[i]-]==str2[i+plen[i]+])
plen[i]++;
if (i+plen[i]>mx)
{
mx=i+plen[i];
id=i;
}
}
}
qword mi2[MAXN];
int main()
{
freopen("input.txt","r",stdin);
int n,m;
int x,y;
int l;
scanf("%s",str);
n=strlen(str);
l=n*+;
mi2[]=;
for (int i=;i<=l;i++)mi2[i]=mi2[i-]*%MOD;
for (int i=;i<n*+;i++)
str2[i]='#';
for (int i=;i<n;i++)
{
if (str[i]=='a')
{
g1[i*+]=g2[i*+]=;
str2[i*+]='a';
}else
{
g1[i*+]=g2[i*+]=-;
str2[i*+]='b';
}
}
manachar(l);
for (l=n*;l!=(l&(-l));l-=l&(-l));
l<<=;
FFT(g1,l,);
FFT(g2,l,);
for (int i=;i<l;i++)g3[i]=g1[i]*g2[i];
FFT(g3,l,-);
for (int i=;i<l;i++)g3[i]=g3[i]/l;
l=n*;
for (int i=;i<l;i++)plen[i]++;
qword ans=;
for (int i=;i<l;i++)
plen2[i]=((min(i,l-i-)+)+round(g3[i*].x))/;
for (int i=;i<l;i++)plen2[i]=(plen2[i]+)/;
for (int i=;i<l;i++)plen[i]=plen[i]/;
for (int i=;i<l;i++)
ans=(ans+mi2[plen2[i]]--plen[i])%MOD;
printf("%lld\n",ans);
return ;
}
上一篇:关于vue的computed、filters、watch


下一篇:yii2.0中url重写实现方法