首页 > 代码库 > ACdreamOJ 1116 斐波那契数列+hash计算后缀
ACdreamOJ 1116 斐波那契数列+hash计算后缀
http://acdream.info/problem?pid=1116
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] )
Input
multiple test cases.
each test case will give you a string consists of lowercase letters, the length of which is no more than 100000.
Output
ouput a number.
Sample Input
aa
Sample Output
3
Hint
样例解释如下:
对于
aa这个后缀,前缀a出现了两次,前缀aa出现了一次,总共三次
对于a这个后缀,前缀a出现了一次
所以答案是f(3) + f(1)
/** ACdreamOJ 1116 (hash 斐波那契数列+hash) 题目大意: 求f(num[i])(i:0~len-1)的和。num[i]表示所有的前缀在以i为起点的后缀中出现的次数。 解题思路: 如果已知num[i],那么利用矩阵连乘就可以求出f(num[i]),因此本题的关键是求出num[i]. 利用hash算法,用has[i]表示以i开头的后缀的哈希值;(hash(i,L)=has(i)-has(i+L)*Hash[L]):表示字符串s[i]~s[i+L]的哈希值. 利用二分求出num1[i](以i为起点的后缀的字符串和原字符串公共前缀的数目)进而num1[]的后缀和就是num[]. */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; typedef unsigned long long LL; const int seed=31; const int maxn=100010; ///============== 斐波那契数列求法============= const int INF=1e9+7; const int MAX=2; struct Matrix { LL m[MAX][MAX]; }; Matrix P= {0,1,1,1}; Matrix I= {1,0,0,1}; Matrix matrixmul(Matrix a,Matrix b)//、矩阵相乘 { Matrix c; for(int i=0; i<MAX; i++) { for(int j=0; j<MAX; j++) { c.m[i][j]=0; for(int k=0; k<MAX; k++) c.m[i][j]+=(a.m[i][k]*b.m[k][j])%INF; c.m[i][j]%=INF; } } return c; } Matrix quickpow(LL n)///矩阵快速幂 { Matrix m=P,b=I; while(n) { if(n&1) b=matrixmul(b,m); n>>=1; m=matrixmul(m,m); } return b; } LL getans(LL t)///返回f(t)的值 { if(t==0) return 0; if(t<2) return 1; Matrix A=quickpow(t-1); return A.m[0][0]+A.m[0][1]; } ///========================================= ///=============字符串后缀哈希值的计算====== LL Hash[maxn],has[maxn],num[maxn]; int len; char s[maxn]; void init()///初始化 { Hash[0]=1; for(int i=1; i<maxn; i++) Hash[i]=Hash[i-1]*seed; } LL get_hash(int i,int L)///得到以i为起点长度为L的后缀的哈希值 { return has[i]-has[i+L]*Hash[L]; } bool ok(int i,int l) { return get_hash(0,l)==get_hash(i,l); } void getnum(int i)///二分,求以i为起点的后缀的字符串和原字符串公共前缀的数目 { int left=i,right=len-1; while(left<=right) { int mid=(left+right)/2; if(ok(i,mid-i+1)) left=mid+1; else right=mid-1; } num[i]=right-i+1; } void makehash()///得到每个后缀的哈希值 { for(int i=len-1; i>=0; i--) { has[i]=has[i+1]*seed+s[i]; } num[0]=len; for(int i=1; i<len; i++) getnum(i); } ///=========================================== int main() { init(); /* int n; while(~scanf("%d",&n)) cout << getans(n)<< endl;*/ while(~scanf("%s",s)) { memset(has,0,sizeof(has)); len=strlen(s); makehash(); for(int i=len-1; i>=0; i--) num[i]+=num[i+1]; LL ans=0; for(int i=0; i<len; i++) ans=(ans+getans(num[i]))%INF; cout << ans << endl; } return 0; }
ACdreamOJ 1116 斐波那契数列+hash计算后缀
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。