{"id":491,"date":"2018-01-18T17:00:18","date_gmt":"2018-01-18T09:00:18","guid":{"rendered":"http:\/\/kylelv.com\/?p=491"},"modified":"2020-03-03T17:46:13","modified_gmt":"2020-03-03T09:46:13","slug":"bzoj-3160-%e4%b8%87%e5%be%84%e4%ba%ba%e8%b8%aa%e7%81%ad-fftmanacher","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=491","title":{"rendered":"bzoj 3160: \u4e07\u5f84\u4eba\u8e2a\u706d — FFT,manacher"},"content":{"rendered":"\n
\n

 <\/p>\n

3160: \u4e07\u5f84\u4eba\u8e2a\u706d<\/h2>\n

Time Limit: <\/span>10 Sec  Memory Limit: <\/span>256 MB<\/p>\n

Description<\/h2>\n
\n

\"\"<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

\"\"<\/p>\n

 <\/p>\n<\/div>\n

Source<\/h2>\n

\u4e0d\u96be\u53d1\u73b0\uff0cans=\u603b\u65b9\u6848 – \u8fde\u7eed\u5b50\u4e32<\/p>\n

\u8003\u8651\u603b\u65b9\u6848\uff0c\u679a\u4e3e\u5bf9\u79f0\u8f74\uff0c\u65b9\u6848\u6570\u5c31\u662f2^f(i) -1\uff0cf(i) \u8868\u793a\u6709\u591a\u5c11\u5bf9\u5173\u4e8e\u5bf9\u79f0\u8f74\u5bf9\u79f0<\/p>\n

\u90a3\u4e48\u5982\u4f55\u6c42f(i)\uff0c\"\"<\/p>\n

\u5f88\u5bb9\u6613\u53d1\u73b0\u5f0f\u5b50\u5c31\u662fFFT\u5377\u79ef\uff0c\u90a3\u5c31\u628aa,b\u62c6\u5f00\u5206\u522b\u6c42\u4e00\u904dFFT\u5c31\u597d\u4e86<\/p>\n

\u8fde\u7eed\u7684\u5c31\u76f4\u63a5manacher\u54af<\/p>\n

#include<map>\n#include<cmath>\n#include<queue>\n#include<cstdio>\n#include<string>\n#include<cstring>\n#include<iostream>\n#include<algorithm>\nusing namespace std;\n#define mod 1000000007\n#define ll long long\n#define N 200010\n#define PI 3.141592653589793\nstruct cp{\n\tdouble r,i;\n\tcp(double _r=0,double _i=0):r(_r),i(_i){}\n\tcp operator + (cp x){return cp(r+x.r,i+x.i);}\n\tcp operator - (cp x){return cp(r-x.r,i-x.i);}\n\tcp operator * (cp x){return cp(r*x.r-i*x.i,r*x.i+i*x.r);}\n\tvoid clr(){r=i=0.0;}\n};\ncp A[N],B[N];\nint r[N],L=-1;\nvoid FFT(cp *x,int n,int f)\n{\n\tregister int i,j,k;\n\tfor(i=0;i<n;i++) if(i<r[i]) swap(x[i],x[r[i]]);\n\tfor(i=1;i<n;i<<=1)\n\t{\n\t\tcp wn(cos(PI\/i),f*sin(PI\/i));\n\t\tfor(j=0;j<n;j+=i<<1)\n\t\t{\n\t\t\tcp w(1,0),X,Y;\n\t\t\tfor(k=0;k<i;k++,w=w*wn)\n\t\t\t{\n\t\t\t\tX=x[k+j];Y=w*x[k+j+i];\n\t\t\t\tx[k+j]=X+Y;x[k+j+i]=X-Y;\n\t\t\t}\n\t\t}\n\t}\n\tif(f==-1) for(int i=0;i<n;i++) x[i].r\/=n;\n}\nchar s[N],a[N];\nint n,m,sum,ans;\nint mx,md,p[N];\nvoid manc()\n{\n\tfor(int i=1;i<=n;i++)\n\t{\n\t\ta[i<<1]=s[i];\n\t\ta[i<<1|1]='#';\n\t}\n\tint nn=n+1<<1;a[0]='!';\n\ta[1]='#';a[nn]='&';\n\tfor(int i=1;i<=nn;i++)\n\t{\n\t\tif(mx>=i) p[i]=min(mx-i,p[2*md-i]);\n\t\telse p[i]=1;\n\t\twhile(a[i-p[i]]==a[i+p[i]]) p[i]++;\n\t\tif(i+p[i]>mx) mx=i+p[i],md=i;\n\t}\n\tfor(int i=2;i<nn;i++) (sum+=p[i]>>1)%=mod;\n}\nint ksm(ll a,int b)\n{\n\tll sum=1;\n\twhile(b)\n\t{\n\t\tif(b&1) sum=sum*a%mod;\n\t\ta=a*a%mod;b>>=1;\n\t}\n\treturn sum;\n}\nint main()\n{\n\tscanf(\"%s\",s+1);\n\tn=strlen(s+1);\n\tmanc();\n\tfor(int i=0;i<n;i++)\n\t{\n\t\tif(s[i+1]=='a') A[i].r=1;\n\t\telse B[i].r=1;\n\t}\n\tfor(m=1;m<(n<<1);m<<=1) L++;\n\tfor(int i=0;i<m;i++) r[i]=r[i>>1]>>1|((i&1)<<L);\n\tFFT(A,m,1);FFT(B,m,1);\n\tfor(int i=0;i<m;i++)\n\t{\n\t\tA[i]=A[i]*A[i];\n\t\tB[i]=B[i]*B[i];\n\t}\n\tFFT(A,m,-1);FFT(B,m,-1);\n\tfor(int i=0,x;i<n+n-1;i++)\n\t{\n\t\tx=(int)(A[i].r+0.1)+(int)(B[i].r+0.1);\n\t\tx=x+1>>1;\n\t\tans+=ksm(2,x)-1;\n\t\tans%=mod;\n\t}\n\tprintf(\"%d\\n\",(ans-sum+mod)%mod);\n\treturn 0;\n}\n<\/pre>\n
 <\/p>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
  3160: \u4e07\u5f84\u4eba\u8e2a\u706d Time Limit: 10 Sec  M […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[38,53],"class_list":["post-491","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-fft","tag-manacher"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/491","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=491"}],"version-history":[{"count":6,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/491\/revisions"}],"predecessor-version":[{"id":589,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/491\/revisions\/589"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=491"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=491"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=491"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}