本文共 4876 字，大约阅读时间需要 16 分钟。

要解决上下对称且左右对称的正方形子矩阵个数的问题，可以使用哈希技术来高效地快速判断子矩阵的对称性。以下是详细的解决方案：

思路概述

详细步骤

代码实现

#include 
   
    
#include 
    
     
using namespace std;
#define di1 1000000007ull
#define di2 1000000009ull
ull times1[1001], times2[1001];
ull hash[1001][1001], hash_up[1001][1001], hash_left[1001][1001];
int n, m, a[1001][1001], ans, tot;
void computeHash() {
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            hash[i][j] = (hash[i][j-1] * di1 + a[i][j]) % di1;
            hash_up[i][j] = (hash_up[i][j-1] * di1 + a[n - i + 1][j]) % di1;
            hash_left[i][j] = (hash_left[i][j-1] * di1 + a[i][m - j + 1]) % di1;
        }
        times1[i] = (times1[i-1] * di1) % di1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            hash[i][j] = (hash[i][j] + hash[i-1][j] * di2) % di1;
            hash_up[i][j] = (hash_up[i][j] + hash_up[i-1][j] * di2) % di1;
            hash_left[i][j] = (hash_left[i][j] + hash_left[i-1][j] * di2) % di1;
        }
    }
}
void ch(int rx, int ry, int dis, int is_up) {
    int lx = rx - dis + 1;
    int ly = ry - dis + 1;
    if (is_up) {
        lx = n - (rx - dis);
        ly = ry - dis + 1;
    } else {
        lx = rx - dis + 1;
        ly = m - (ry - dis);
    }
    if (lx < 1 || lx > n || ly < 1 || ly > m) return 0;
    int hash_val = 0;
    if (is_up) {
        hash_val = hash_up[rx][ry] - hash_up[rx][ly - 1] * times1[dis] - hash_up[lx - 1][ry] * times2[dis] + hash_up[lx - 1][ly - 1] * times1[dis] * times2[dis];
    } else {
        hash_val = hash[rx][ry] - hash[rx][ly - 1] * times1[dis] - hash[lx - 1][ry] * times2[dis] + hash[lx - 1][ly - 1] * times1[dis] * times2[dis];
    }
    hash_val %= di1;
    return hash_val;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            a[i][j] = (a[i][j] + a[i][j-1]) % di1;
            int up_row = n - i + 1;
            a[up_row][j] = (a[up_row][j] + a[up_row][j-1]) % di1;
            int left_col = m - j + 1;
            a[i][left_col] = (a[i][left_col] + a[i][left_col-1]) % di1;
        }
    }
    times1[0] = 1;
    times2[0] = 1;
    for (int i = 1; i <= n; ++i) {
        times1[i] = (times1[i-1] * di1) % di1;
    }
    for (int i = 1; i <= m; ++i) {
        times2[i] = (times2[i-1] * di2) % di2;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            a[i][j] = (a[i][j] + a[i-1][j] * di2) % di1;
            int up_row = n - i + 1;
            a[up_row][j] = (a[up_row][j] + a[up_row-1][j] * di2) % di1;
            int left_col = m - j + 1;
            a[i][left_col] = (a[i][left_col] + a[i][left_col-1] * di2) % di1;
        }
    }
    tot = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int max_len = min(i, n - i + 1);
            max_len = min(max_len, j);
            max_len = min(max_len, m - j + 1);
            int odd = 1;
            int l = 1, r = 0;
            while (l <= r) {
                mid = (l + r) >> 1;
                if (i - mid + 1 < 1 || i + mid - 1 > n || j - mid + 1 < 1 || j + mid - 1 > m) {
                    r = mid - 1;
                    continue;
                }
                int x = i + mid - 1;
                int y = j + mid - 1;
                if (ch(x, y, mid, 0)) {
                    tot += mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            l = 1, r = min(i, n - i);
            r = min(r, j);
            r = min(r, m - j);
            while (l <= r) {
                mid = (l + r) >> 1;
                if (i - mid + 1 < 1 || i + mid > n || j - mid + 1 < 1 || j + mid > m) {
                    r = mid - 1;
                    continue;
                }
                int x = i + mid;
                int y = j + mid;
                if (ch(x, y, mid, 1)) {
                    tot += mid;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
    }
    printf("%d", tot);
    return 0;
}
    
   

代码解释

通过这种方法，可以高效地解决问题，避免直接比较子矩阵元素的高时间复杂度，确保在合理时间内完成计算。