这个哈希映射其实就是要把一个串映射到一个域当中，如果模数为MMM的话，实际上是把一个串映射到{0,1,2,...,M−1}\left\{ 0 ,1,2,...,M-1\right\}{0,1,2,...,M−1}，那么如果这个basebasebase基底，与MMM互质，则有可能映射到域上的所有数。这个是离散里面的。
所以basebasebase取质数最好，避免了{4,8,12,..}\left\{ 4,8,12,..\right\}{4,8,12,..}这样转。
如果是长度为200020002000的262626个字母可以使用的基底为131131131和模数ullullull
题目体会：F. 地图压缩
代码：

#include 
#include 
#include 
using namespace std;
typedef unsigned long long ull;
ull dp[3000][3000];
int mod = 1e9 + 7;
ull hash_row[3000][3000];
ull hash_col[3000][3000];mt19937 R(mod);
int n, q;
int kmp(vector &tmp)
{int n = tmp.size();vector f(n + 5, 0);for (int i = 0; i < n; i++)f[i] = -1;int i = 0;int j = 1;while (j < n){if (tmp[i] == tmp[j]){f[j] = i;j++;i++;}else if (i == 0){f[j] = -1;j++;}else{i = f[i - 1] + 1;}}return n - f[n - 1] - 1;}
int main()
{scanf_s("%d%d", &n, &q); getchar();for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){char c;scanf_s("%c", &c);dp[i][j] = c - 'a';//scanf_s("%lld", &dp[i][j]);}getchar();}//先对行做哈希//再对列做哈希int base =55;//R() % mod + 1;//35可以,32bu，33可以，30bu,42不，45ke,46bu,48bu,49kevector pw(n + 5, 0);pw[0] = 1;for (int i = 1; i <= n; i++)pw[i] = pw[i - 1] * base;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){hash_row[i][j] = hash_row[i][j - 1] + pw[j] * dp[i][j];}}for (int j = 1; j <= n; j++){for (int i = 1; i <= n; i++){hash_col[i][j] = hash_col[i - 1][j] + pw[i] * dp[i][j];}}for (int i = 0; i < q; i++){int a, b, c, d;scanf_s("%d%d%d%d", &a, &b, &c, &d);//先对行哈希做kmpvector tmp_row;for (int k = a; k <= c; k++){tmp_row.push_back(hash_row[k][d] - hash_row[k][b - 1]);}int yh_row = kmp(tmp_row);vector tmp_col;for (int k = b; k <= d; k++){tmp_col.push_back(hash_col[c][k] - hash_col[a - 1][k]);}int yh_col = kmp(tmp_col);printf("%d\n", yh_row*yh_col);}
}

如果长度是2e52e52e5的数范围也在2e52e52e5的话，可以使用基底为mt19937mt19937mt19937和ullullull
题目体会：E. Labeling the Tree with Distances

#include
#include
#include
#include
#include