乱七八糟的模板集合

字符串

1.字符串哈希（可以用于直接比较字符串相同，找循环节[hash(l, r - x) == hash(l + x, r) 可判定x为一个循环节])

 1 // 采用自然溢出
 2 typedef unsigned long long ull;
 3 const short base = 131;
 4 ull hashs[maxn],bases[maxn];
 5 void init() {
 6     bases[0] = 1;
 7     for(int i = 1; i <= n; ++i) {
 8         bases[i] = bases[i - 1] * base;
 9         hashs[i] = hashs[i - 1] * base + str[i] - 'a' + 1;
10     }
11 }
12 ull get_hash(int l, int r) {
13     return hashs[r] - hashs[l - 1] * bases[r - l + 1];
14 }