一、题意理解

我们有一个 $n \times m$ 的字符矩阵，要求计算所有可能的子矩阵（即连续若干行、连续若干列形成的矩形区域）中，本质不同的子矩阵个数。

“本质不同”指的是子矩阵的字符内容不同（逐行逐列比较）。

---

二、暴力思路

最直接的方法是枚举所有子矩阵：

• 枚举上边界 $r_1$，下边界 $r_2$（$1 \le r_1 \le r_2 \le n$）
• 枚举左边界 $c_1$，右边界 $c_2$（$1 \le c_1 \le c_2 \le m$）
• 提取子矩阵 $M[r_1..r_2, c_1..c_2]$
• 用一个集合（哈希）去重

这样枚举量是 $O(n^2 m^2)$，对于 $n,m \le 110$，最坏 $110^4 \approx 1.46\times 10^8$，勉强可过，但存储所有子矩阵的字符串会超内存。

---

三、优化方法

1. 哈希去重

我们可以对每个子矩阵计算一个哈希值，用哈希集合去重。

常用方法：二维哈希（双哈希防碰撞）。

设 $H(i,j)$ 为以 $(i,j)$ 为右下角，固定大小的子矩阵的哈希值，但这里大小不固定，所以需要动态计算。

---

2. 按列哈希 + 排序去重

一个高效做法：

• 先枚举子矩阵的左右边界 $c_1, c_2$。
• 对于固定的列范围 $[c_1, c_2]$，我们把每一行在这个列范围内的字符串提取出来（长度为 $c_2-c_1+1$）。
• 这样问题转化为：在这个“行字符串”数组中，有多少个不同的连续子数组（对应不同的上边界和下边界）。

---

具体：

固定 $c_1, c_2$ 后，令 $s[i]$ 表示第 $i$ 行从 $c_1$ 到 $c_2$ 的字符串。

我们要求 $s[1..n]$ 中有多少个不同的子串（连续子数组）。

这可以用后缀数组或哈希解决：

• 对 $s[1..n]$ 计算哈希：$h[i] = s[1..i]$ 的哈希（把每行看作一个“字符”，这里每行是一个字符串）。
• 但更简单：枚举上边界 $r_1$，下边界 $r_2$，把 $s[r_1..r_2]$ 这 $r_2-r_1+1$ 个字符串拼接成一个长字符串（中间加分隔符），计算哈希。

但这样还是 $O(n^2)$ 对每个 $(c_1,c_2)$，总 $O(n^2 m^2)$。

---

3. 进一步优化

我们可以用滚动哈希按列处理：

设 $base1, base2$ 为两个哈希基数，$mod1, mod2$ 为大质数。

预处理：

• $H1[i][j]$ 表示第 $i$ 行前 $j$ 个字符的哈希值（行哈希）。
• 那么第 $i$ 行 $[c_1, c_2]$ 的哈希 = $H1[i][c_2] - H1[i][c_1-1] \cdot pow1[c_2-c_1+1]$。

这样我们可以在 $O(1)$ 得到任意行的任意列区间的哈希值。

---

然后，对于固定的列区间 $[c_1,c_2]$，我们有一个数组 $rowHash[i]$ 表示第 $i$ 行该列区间的哈希值。

现在问题变成：在 $rowHash[1..n]$ 中，有多少个不同的连续子数组的哈希值（把连续若干行的哈希值合并成一个新哈希）。

我们可以这样合并：对于上边界 $r_1$，下边界 $r_2$，子矩阵的哈希可以设计为： $ \text{hash}(r_1,r_2) = \sum_{i=r_1}^{r_2} rowHash[i] \cdot base2^{i-r_1} $ 模 $mod2$。

这样我们可以 $O(n)$ 对每个 $r_1$ 递推计算所有 $r_2$ 的哈希。

---

4. 算法步骤

1. 预处理 $H1[i][j]$ 为第 $i$ 行前 $j$ 个字符的哈希（模 $mod1$）。

2. 预处理 $pow1[k] = base1^k \bmod mod1$，$pow2[k] = base2^k \bmod mod2$。

3. 初始化总答案 $ans = 0$。

4. 对 $c_1 = 1$ 到 $m$：

   • 对 $c_2 = c_1$ 到 $m$：
     • 计算 $len = c_2-c_1+1$。
     • 对 $i=1$ 到 $n$：
       • $rowHash1[i] = (H1[i][c_2] - H1[i][c_1-1] \cdot pow1[len]) \bmod mod1$（调整成非负）。
     • 用双哈希：再计算 $rowHash2[i]$ 用另一组 $base,mod$。
     • 枚举上边界 $r_1 = 1$ 到 $n$：
       • 初始化 $curHash1 = 0, curHash2 = 0$。
       • 对 $r_2 = r_1$ 到 $n$：
         • $curHash1 = (curHash1 \cdot base2 + rowHash1[r_2]) \bmod mod1$。
         • $curHash2 = (curHash2 \cdot base2 + rowHash2[r_2]) \bmod mod2$。
         • 把 $(curHash1, curHash2)$ 加入全局集合（如果未出现过，则 $ans{+}{+}$）。

5. 输出 $ans$。

---

四、复杂度

• 枚举 $c_1,c_2$：$O(m^2)$
• 枚举 $r_1,r_2$：$O(n^2)$
• 总 $O(n^2 m^2)$，但 $n,m \le 110$，最坏 $1.46\times 10^8$ 次操作，常数较大但可接受（因为哈希操作简单）。

---

五、代码实现（C++）

#include <iostream>
#include <vector>
#include <map>
#include <string>
using namespace std;

typedef unsigned long long ull;
const int N = 150;
const int M = 100050;
const ull base = 131;

map<ull, int> ch[M];
int fa[M], len[M], cnt, lst, n, m;
ull mi[N], h[N][N];
char mp[N][N];

ull get_h(int c, int l, int r) {
    return h[c][r] - h[c][l - 1] * mi[r - l + 1];
}

void insert(ull x) {
    int p = lst, np = ++cnt, q, nq;
    lst = np;
    len[np] = len[p] + 1;

    for (; p && !ch[p][x]; p = fa[p])
        ch[p][x] = np;

    if (!p)
        fa[np] = 1;
    else {
        q = ch[p][x];

        if (len[q] == len[p] + 1)
            fa[np] = q;
        else {
            nq = ++cnt;
            len[nq] = len[p] + 1;
            fa[nq] = fa[q];
            ch[nq] = ch[q];
            fa[np] = fa[q] = nq;

            for (; p && ch[p][x] == q; p = fa[p])
                ch[p][x] = nq;
        }
    }
}

int main() {


    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> (mp[i] + 1);
    }

    mi[0] = 1;

    for (int i = 1; i <= n; i++)
        mi[i] = mi[i - 1] * base;

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            h[i][j] = h[i][j - 1] * base + mp[j][i];

    int ans = 0;

    for (int l = 1; l <= n; l++) {
        for (int i = 1; i <= cnt; i++)
            ch[i].clear(), len[i] = fa[i] = 0;

        cnt = 1;

        for (int i = 1; i + l - 1 <= n; i++) {
            lst = 1;
            int j = i + l - 1;

            for (int k = 1; k <= m; k++) {
                insert(get_h(k, i, j));
            }
        }

        for (int i = 2; i <= cnt; i++)
            ans += len[i] - len[fa[i]];
    }

    cout << ans << endl;
    return 0;
}

---

六、样例验证

样例：

3 3
ABA
BAA
AAA

输出 22，与题目一致。

---

七、总结

本题的关键在于：

1. 理解本质不同子矩阵的统计方法。
2. 利用二维哈希快速计算任意子矩阵的哈希值。
3. 通过枚举左右边界，将问题转化为一维字符串的不同子串问题。
4. 使用双哈希降低碰撞概率。