设为首页 加入收藏

TOP

Acdreamoj1116（Gao the string!）字符串hash+二分+矩阵快速幂
2015-07-24 06:00:10 来源: 作者: 【大 中 小】 浏览:10次
Tags：Acdreamoj1116 Gao the string 字符串 hash +二分 矩阵 快速

Problem Description

give you a string, please output the result of the following function mod 1000000007

\

n is the length of the string

f() is the function of fibonacci, f(0) = 0, f(1) = 1...

a[i] is the total number of times any prefix appear in the suffix s[i....n-1].

(the prefix means s[0...i] )

解法：如果知道了num[i]表示i开始的后缀s[i....n]跟前缀s[1...]之间的公共的前缀，那么以i开头的后缀中就匹配了num[i]个前缀了

所以i这个后缀出现的前缀的数量实际上就是num[i] + num[i+1] + .. num[n]. 求出来之后快速幂求斐波那契数列相应项大小即可。求lcp的时候是二分+hash；字符串hash中，seed为31（java库源码中是这个数，应该是效果比较好的）

代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const int INF=1000000007; const int hashseed=31; LL seed[Max]; LL has[Max]; char s[Max]; LL num[Max]; int len=0; struct matrix { LL num[2][2]; matrix() { memset(num,0,sizeof num); } }; matrix operator*(const matrix& a,const matrix& b) { matrix ans; for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) ans.num[j][k]+=(a.num[j][i]*b.num[i][k])%INF; return ans; } matrix operator^(matrix a,LL n) { matrix ans; ans.num[0][0]=1; ans.num[1][1]=1; while(n) { if(n&1) { ans=ans*a; } a=a*a; n>>=1; } return ans; } LL getans(LL t) { if(t==0) return 0; if(t<=2) return 1; matrix tool; tool.num[0][0]=1; tool.num[0][1]=1; tool.num[1][0]=1; tool=tool^(t-1); return tool.num[0][0]%INF; } void init() { seed[0]=1; for(int i=1; i
              
               =0;i--) { has[i]=(has[i+1]*hashseed+s[i])%INF; } num[0]=len; for(int i=1;i
               
                =0;i--) num[i]+=num[i+1]; LL ans=0; for(int i=0;i
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：c++实现二叉搜索树 下一篇：POJ 3104 Drying 二分

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: