「BZOJ3160」万径人踪灭
大爷题解传送门：
http://blog.csdn.net/popoqqq/article/details/42193259
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include<cmath> #include<cstdio> #include<complex> #include<cstring> #include<iostream> #include<algorithm> #define pi acos(-1) #define ll long long #define inf 1000000000 #define mod 1000000007 #define N 262144 using namespace std; typedef complex<double> E; ll ans; int n,m,len,L; E a[N],f[N],g[N]; char ch[N]; int R[N],p[N],bin[N]; void fft(E *a,int f) { for(int i=1;i<n;i++) if(i>R[i])swap(a[i],a[R[i]]); for(int i=1;i<n;i<<=1) { E wn(cos(pi/i),sin(pi/i)*f); for(int j=0;j<n;j+=(i<<1)) { E w(1,0); for(int k=0;k<i;k++,w*=wn) { E 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]/=n; } void manacher() { ch[0]='-';ch[len+1]='+'; int id,mx=0; for(int i=1;i<=len;i++) { if(mx>i)p[i]=min(mx-i+1,p[2*id-i]); else p[i]=1; while(ch[i+p[i]]==ch[i-p[i]])p[i]++; if(i+p[i]-1>mx)mx=i+p[i]-1,id=i; ans-=p[i];ans%=mod; } mx=0; for(int i=1;i<=len;i++) { if(mx>i)p[i]=min(mx-i,p[2*id-i]); else p[i]=0; while(ch[i+p[i]+1]==ch[i-p[i]])p[i]++; if(i+p[i]>mx)mx=i+p[i],id=i; ans-=p[i];ans%=mod; } } int main() { bin[0]=1;for(int i=1;i<=100000;i++)bin[i]=bin[i-1]*2%mod; scanf("%s",ch+1); len=strlen(ch+1); manacher(); m=2*(len-1);for(n=1;n<=m;n<<=1)L++; for(int i=1;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); for(int i=0;i<len;i++)a[i]=(ch[i+1]=='a'); fft(a,1);for(int i=0;i<n;i++)f[i]=a[i]*a[i]; fft(f,-1); memset(a,0,sizeof(a)); for(int i=0;i<len;i++)a[i]=(ch[i+1]=='b'); fft(a,1);for(int i=0;i<n;i++)g[i]=a[i]*a[i]; fft(g,-1); for(int i=0;i<n;i++) { int x=f[i].real()+g[i].real()+0.1; ans+=bin[(x+1)/2]; ans--; ans%=mod; } printf("%lld\n",(ans+mod)%mod); return 0; } |
Subscribe
计数器 9320207
OI 课件=>
OI 课件=>