注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3160]万径人踪灭  

2015-05-14 15:02:30|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3160: 万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 188  Solved: 105
[Submit][Status][Discuss]

Description

Solution

蛮有意思的一道题
对于子序列回文,只要求出以当前某个点为回文中心的回文串,就是求有多少个字母对称轴在这个字母位置上,用FFT解决。
扣掉不合法的方案,用回文自动机实现。

Code

/**************************************************************
    Problem: 3160
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4168 ms
    Memory:22720 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 1<<18|10
typedef double ld;ld pi=acos(-1);
struct P{ld x,y;}tmp;
#define PP const P&
P operator+(PP a,PP b){return (P){a.x+b.x,a.y+b.y};}
P operator-(PP a,PP b){return (P){a.x-b.x,a.y-b.y};}
P operator*(PP a,PP b){return (P){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};}
P x[N],y[N],w[2][N];int f[N],rev[N],n,i,l;long long ans;char s[N];
void FFT(P*a,P*w){int i,j,k;
    for(i=1;i<n;i++)if(i>rev[i])std::swap(a[i],a[rev[i]]);
    for(i=2;i<=n;i<<=1)
    for(j=0;j<n;j+=i)
    for(k=0;k<i>>1;k++)
    tmp=a[j+k+i/2]*w[n/i*k],a[j+k+i/2]=a[j+k]-tmp,a[j+k]=a[j+k]+tmp;
}
#define mod 1000000007
int power(int k){int f=1,t=2;
    for(;k;k>>=1,t=1LL*t*t%mod)
    if(k&1)f=1LL*f*t%mod;
    return f;
}
#define M 100010
int ch[M][2],fail[M],tot,las,now,len[N],cnt[N];
int nn(int l){len[tot]=l;return tot++;}
int gf(int x,int n){
    while(n-len[x]-1<0||s[n]!=s[n-len[x]-1])x=fail[x];
    return x;
}
int main(){
    for(gets(s),i=0;s[i];i++);
    for(n=1;n<i;n<<=1,l++);n<<=1;
    for(i=0;i<=n;i++){
        w[1][n-i]=w[0][i]=(P){cos(pi*2*i/n),sin(pi*2*i/n)};
        rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
    }
    for(i=0;s[i];i++)if(s[i]=='a')x[i].x++;else y[i].x++;
    FFT(x,w[0]),FFT(y,w[0]);
    for(i=0;i<n;i++)x[i]=x[i]*x[i],y[i]=y[i]*y[i];
    FFT(x,w[1]),FFT(y,w[1]);
    for(i=0;i<n;i++)f[i]=((int(x[i].x/n+0.5)+1)>>1)+((int(y[i].x/n+0.5)+1)>>1);
    for(i=0;i<n;i++)if(f[i])ans=(ans+power(f[i])-1)%mod;
    for(nn(0),nn(-1),fail[0]=1,i=0;s[i];i++){
        s[i]-='a';las=gf(las,i);
        if(!ch[las][s[i]]){
            now=nn(len[las]+2);
            fail[now]=ch[gf(fail[las],i)][s[i]];
            ch[las][s[i]]=now;
        }
        cnt[las=ch[las][s[i]]]++;
    }
    for(i=--tot;i>1;i--)cnt[fail[i]]+=cnt[i],ans=(ans-cnt[i]+mod)%mod;
    printf("%lld\n",ans);
}
  评论这张
 
阅读(25)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018