字符串 Hash

luckydrawbox · 2022-02-25 13:27:11 · 个人记录

宏定义

• #define ull unsigned long long：\text{Hash} 时常用 \text{unsigned long long} 类型。

常量和变量

函数

#define ull unsigned long long
struct Hash{
    const ull P=13331;
    //const mod=;
    char ji='a';
    ull qmi(int a){
        ull ans=1,b=P;
        while(a){
            if(a&1)
                ans*=b;
            b=b*b;
            a>>=1;
        }
        return ans;
    }
    ull ask(string s){
        ull f=int(s[0]-ji);
        int l=s.size();
        for(int i=1;i<l;i++){
            f=f*P;
            f+=int(s[i]-ji);
        }
        return f;
    }
    ull jia(ull a,ull b,int b_size){
        return a*qmi(b_size)+b;
    }
    ull jian(ull a,ull b,int s_size){
        return a-b*qmi(s_size);
    }
};