首页 > 代码库 > BZOJ 3160 万径人踪灭 Manacher算法+快速傅里叶变换
BZOJ 3160 万径人踪灭 Manacher算法+快速傅里叶变换
题目大意:给定一个由‘a‘和‘b‘构成的字符串,求不连续回文子序列的个数
首先回文一定是将字符串倍增 由于求的是不连续回文子序列的个数 因此我们可以求出总回文子序列的个数,然后减掉连续的
连续的就是回文子串 用Manacher算法可以O(n)求解
不连续的就有些难搞了
首先我们令f[i]表示以i为中心的对称字符对个数
比如s[]=$#a#b#a 那么s[4]=‘b‘ f[4]=2
那么对于每个中心i我们有(2^f[i])-1种方案 答案即Σ[1<=i<=n*2+1]((2^f[i])-1)
问题就是如何求出f[]数组
我们发现对f[i]有贡献的一对字符在原字符串数组中的位置之和一定是i
比如str+1="aba" 那么第一个字符和第三个字符对倍增后的字符串的第4个位置有贡献
那么显然有f[i]=(Σ[1<=j<=i-1]bool(str[j]==str[i-j]))+1>>1 括号里面是一个卷积的形式 可以用FFT进行求解
首先考虑‘a‘对答案的贡献 那么令‘a‘=1 ‘b‘=0 求出卷积就是‘a‘的贡献
再考虑‘b‘对答案的贡献 令‘a‘=0 ‘b‘=1 求出卷积就是‘b‘的贡献
两次贡献之和+1>>1就是f[]数组 代入之前的结论中即可出解
同学居然拿这个来出题- - 尼玛还我还真推出FFT了- - 还尼玛写挂了- -没开long long被干掉5个点TAT
大脑不好使了 哪里写的不明白或者写错了就在下面回复一下吧- - 看代码也行- -
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 263000 #define MOD 1000000007 #define PI 3.141592653589793238462643 using namespace std; typedef long long ll; struct Complex{ double a,b; Complex() {} Complex(double _,double __):a(_),b(__) {} void operator += (const Complex &x) { a+=x.a; b+=x.b; } Complex operator - (const Complex &x) const { return Complex(a-x.a,b-x.b); } Complex operator * (const Complex &x) const { return Complex(a*x.a-b*x.b,a*x.b+b*x.a); } void operator *= (const Complex &x) { *this=(*this)*x; } Complex operator + (const Complex &x) { Complex re=*this; re+=x;return re; } }a[M],b[M]; char s[M]; int f[M<<1],power[M],temp[M],ans; int Manacher(char str[],int n) { static char s[M<<1]; static int f[M<<1]; int i,re=0; for(s[0]='$',s[1]='#',i=1;i<=n;i++) s[i<<1]=str[i],s[i<<1|1]='#'; n=n<<1|1; int mx=1,id=1; for(i=1;i<=n;i++) { f[i]=min(f[id+id-i],mx-i); while(s[i+f[i]]==s[i-f[i]]) f[i]++; if(f[i]+i>mx) mx=f[i]+i,id=i; re+=f[i]>>1,re%=MOD; } return re; } void FFT(Complex x[],int n,int type) { static Complex temp[M]; if(n==1) return ; int i; for(i=0;i<n;i+=2) temp[i>>1]=x[i],temp[i+n>>1]=x[i+1]; memcpy(x,temp,sizeof(Complex)*n); Complex *l=x,*r=x+(n>>1); FFT(l,n>>1,type);FFT(r,n>>1,type); Complex root( cos(type*2*PI/n) , sin(type*2*PI/n) ),w(1,0); for(i=0;i<n>>1;i++,w*=root) temp[i]=l[i]+w*r[i],temp[i+(n>>1)]=l[i]-w*r[i]; memcpy(x,temp,sizeof(Complex)*n); } void Pretreatment() { int i; power[0]=1; for(i=1;i<M;i++) power[i]=(power[i-1]<<1)%MOD; } int main() { scanf("%s",s+1); int i,n,len=strlen(s+1); Pretreatment(); for(n=1;n<=len<<1;n<<=1); for(i=1;i<=len;i++) if(s[i]=='a') a[i].a=1; FFT(a,n,1); for(i=0;i<n;i++) b[i]=a[i]*a[i]; memset(a,0,sizeof a); for(i=1;i<=len;i++) if(s[i]=='b') a[i].a=1; FFT(a,n,1); for(i=0;i<n;i++) b[i]+=a[i]*a[i]; FFT(b,n,-1); for(i=1;i<n;i++) temp[i]+=ll(b[i].a+0.5)/n; for(i=1;i<n;i++) ans+=power[temp[i]+1>>1]-1,ans%=MOD; cout<<(ans+MOD-Manacher(s,len))%MOD<<endl; }
BZOJ 3160 万径人踪灭 Manacher算法+快速傅里叶变换
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。