【BZOJ3160】萬徑人蹤滅

Description

Input

Output

Sample Input

Sample Output

HINT

題解：自己想出來1A，先撒花~（其實(shí)FFT部分挺裸的）

做這道題，第一思路很重要，顯然看到這題的第一想法就是ans=總數(shù)-不合法（不要問我為什么顯然）。因?yàn)橄蜻@種用補(bǔ)集法的題一般都會(huì)給一些很奇葩的限制條件，但是一旦換個(gè)角度去想就很水了，好了不多說廢話了。

顯然，不合法的情況，也就是連續(xù)的回文區(qū)間的方案數(shù)，我們直接上Manacher就搞定了嘛！答案就是所有對(duì)稱軸的（最長(zhǎng)回文串長(zhǎng)度+1）/2之和（是的，很顯然）

對(duì)于不合法的情況，我們發(fā)現(xiàn)兩串對(duì)稱的情況跟卷積的形式類似（FFT做多了吧？），但是問題來了，怎么構(gòu)造出一個(gè)卷積，使得它的值就是回文子串的個(gè)數(shù)呢？

我們發(fā)現(xiàn)原串只有a或b，所以思考能不能構(gòu)造出一種卷積，使得對(duì)應(yīng)位置的值跟下面一樣

a*b->0 ? ? ? b*a->0 ? ? ? ?a*a->1 ? ? b*b->1

如果把a(bǔ)看成0，b看成1，這顯然是一個(gè)異或，然而并沒什么卵用。但我們?nèi)绻補(bǔ)看成0，b看成1，可以滿足只有b*b是1，其他都是0；同理，把a(bǔ)看成1，b看成0，可以滿足只有a*a是1，其他都是0，然后我們對(duì)這兩種情況分別求一次卷積，就能得到：以i為對(duì)稱中心的最長(zhǎng)子序列的回文半徑長(zhǎng)度。這里注意一下，用于是兩個(gè)一樣的多項(xiàng)式相乘，所以每對(duì)字符會(huì)被算成兩次（單個(gè)字符自我對(duì)稱的除外），所以我們要的回文半徑應(yīng)該是(x+1)/2

然而半徑長(zhǎng)度并不是方案數(shù)，由于每對(duì)對(duì)稱的字符都可以選或不選，所以對(duì)答案的貢獻(xiàn)就是2^長(zhǎng)度-1（因?yàn)槟悴荒芤粋€(gè)也不選吧？）

好吧，感覺說了這么多又有點(diǎn)說不明白了，所以歡迎提問和hack~

#include <cstdio> #include <cstring> #include <iostream> #include <cmath> #define pi acos(-1.0) #define mod 1000000007 using namespace std; int n,ans; struct cp {double x,y;cp (double a,double b){x=a,y=b;}cp (){}cp operator + (cp a){return cp(x+a.x,y+a.y);}cp operator - (cp a){return cp(x-a.x,y-a.y);}cp operator * (cp a){return cp(x*a.x-y*a.y,x*a.y+y*a.x);} }n1[1<<20],n2[1<<20]; int s[1<<20],ret[1<<20],rl[1<<20],pn[1<<20]; char str[1<<20]; void FFT(cp *a,int len,int f) {int i,j,k,h;cp t;for(i=k=0;i<len;i++){if(i>k) swap(a[i],a[k]);for(j=(len>>1);(k^=j)<j;j>>=1);}for(h=2;h<=len;h<<=1){cp wn(cos(f*2*pi/h),sin(f*2*pi/h));for(j=0;j<len;j+=h){cp w(1.0,0);for(k=j;k<j+h/2;k++) t=w*a[k+h/2],a[k+h/2]=a[k]-t,a[k]=a[k]+t,w=w*wn;}} } void work(cp *a,cp *b,int len) {FFT(a,len,1),FFT(b,len,1);for(int i=0;i<len;i++) a[i]=a[i]*b[i];FFT(a,len,-1);for(int i=0;i<len;i++) ret[i]+=(int)(a[i].x/len+0.1); } int main() {scanf("%s",str);int i,mx,pos,len=strlen(str);for(i=0;i<len;i++) s[n++]=0,s[n++]=str[i]-'a';s[n++]=0;for(mx=-1,i=0;i<n;i++){if(mx>i) rl[i]=min(mx-i+1,rl[2*pos-i]);else rl[i]=1;for(;i+rl[i]<n&&rl[i]<=i&&s[i+rl[i]]==s[i-rl[i]];rl[i]++);if(mx<i+rl[i]-1) mx=i+rl[i]-1,pos=i;}for(i=0;i<n;i++) ans=(ans-rl[i]/2+mod)%mod;for(len=1;len<2*n;len<<=1);for(i=0;i<len;i++) n1[i]=n2[i]=cp(0,0);for(i=1;i<n;i+=2) n1[i]=n2[i]=cp(s[i],0);work(n1,n2,len);for(i=0;i<len;i++) n1[i]=n2[i]=cp(0,0);for(i=1;i<n;i+=2) n1[i]=n2[i]=cp(s[i]^1,0);work(n1,n2,len);for(pn[0]=i=1;i<=n;i++) pn[i]=(pn[i-1]<<1)%mod;for(i=0;i<n;i++) ans=(ans+pn[(ret[i<<1]+(i&1))>>1]-1)%mod;printf("%d",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/CQzhangyu/p/6890700.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ3160】万径人踪灭 Manacher+FFT的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。