Hash

对于一个主串和一个子串，我们想知道它们是否匹配，暴力肯定不可取，如果我们用一个数来表示它们中的每一个字符以及子串呢？字符串hash就出现了
\(f(s)=s[1]*base^{len-1}+s[2]*base^{len-2}+…+s[len]*base^{0}\)

很显然，字符串的hash值的计算是类比于十进制数的个十百位叠加，而不是单纯的字符数值的叠加（例如ab和ba，两个字符串的字符一样，顺序不一样）
那我们就可以去计算一个任意串的hash值了

ull hash(int len){
	ull res=1;
	for(int i=1;i<=len;i++){
		res=(res*base+s[i]);
	}
	return res;
}

这里取值要取模，因为只是去判断数值是否相等，不用比较数值大小，且稍大一点的数会炸int甚至long long，所以要取模
取模方法：
1.自然溢出unsigned long long，这个变量名下的变量不会是负的，对于超出范围的值自动模上\(2^{64}\)，这样方便高效，唯一的缺点是很容易被卡
2.单模，找一个大质数去取模，hash值就在0到质数之间
3.双模，找两个质数去取模，如果取模完的值都一样，那么这两个子串就一样

但是求单个的hash值太慢，有时候我们要将一个主串与多个字符串匹配，这个时候，每个子串长度不一，就会T掉，那么我们就要通过前缀和来快速求出主串的hash值
前面提到，hash值的计算是基于类似十进制数的加减，那么我们可以利用这个性质举个栗子：
如果我想让12345与45的值相等，那么我可以让123*\(10^2\)，再用12345减去这个值，那么就能和45相等了
类比于字符串：
令\(f_i(s)\)表示f(s[1…i])的哈希值
所以会有\(f_i(s)=s[1]*base^{i-1}+s[2]*base^{i-2}+…+s[i]\)

所以得出
\(f(s[l…r])=f_r(s)-f_{l-1}(s)*base^{r-l+1}\)
对应的图

void solve(){
	for(int i=1;i<=len;i++){
		has[i]=has[i-1]*base+c[i];
	}
}
void ba(){
	bas[0]=1;
	for(int i=1;i<=400000;i++){
		bas[i]=bas[i-1]*base;
	}
}
ull check(int from,int to){
	return has[to]-has[from-1]*bas[to-from+1];
}