程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Acdreamoj1116（Gao the string!）字符串hash+二分+矩陣快速冪

Acdreamoj1116（Gao the string!）字符串hash+二分+矩陣快速冪

編輯：C++入門知識

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