题解 | 2023 年牛客多校第三场 G 题 Beautiful Matrix

题意：给定一个 $n\times mn\backslash times\; m$ 的字符矩阵 $\{S{\}}_{(i,j)=(1,1)}^{(n,m)}\backslash \{S\backslash \}\_\{(i,j)=(1,1)\}^\{(n,m)\}$，定义一个 $n\times nn\backslash times\; n$ 的子矩阵是优美的当且仅当 $\mathrm{\forall }i,j\in [1,n]\backslash forall\; i,j\; \backslash in\; [1,n]$，$S_{i,j}=S_{n-i+1,n-j+1}S\_\{i,j\}=S\_\{n-i+1,n-j+1\}$。问 $\{S\}\backslash \{S\backslash \}$ 中有多少个优美的子矩阵。$1\le n,m\le 2\times 10^{3}1\backslash le\; n,m\; \backslash le\; 2\backslash times\; 10^3$。

解法：本题卡常，请使用 $\mathcal{O}(n^2)\backslash mathcal\; O(n^2)$ 的做法通过。

首先枚举哪一行是中央对称行。当固定中央行之后，考虑在这一行做 Manacher。传统的 Manacher 是仅单字符匹配成立即可扩展回文半径，在本题这种矩阵对称中，可以考虑对一个矩阵区域（正向绿色等于反向紫色）的匹配作为扩展条件：

因而使用二维哈希判断子矩阵对称相等，结合 Manacher 算法即可通过。复杂度同每行 Manacher 算法，即 $O(nm)O(nm)$。

本题严重卡常。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
int a[N + 5][N + 5], n, m;
struct Hash1
{
    const int p1 = 31, p2 = 1331, mod = 1e9 + 9;
    void add(int &x, int y)
    {
        if ((x += y) >= mod)
            x -= mod;
    }
    void sub(int &x, int y)
    {
        if ((x -= y) < 0)
            x += mod;
    }
    int invth1[N + 5], invth2[N + 5];
    int Pow1[N + 5], Pow2[N + 5];
    int sum1[N + 5][N + 5], sum2[N + 5][N + 5];
    int power(int a, int x)
    {
        int ans = 1;
        while (x)
        {
            if (x & 1)
                ans = 1ll * ans * a % mod;
            a = 1ll * a * a % mod;
            x >>= 1;
        }
        return ans;
    }
    int inv(int a)
    {
        return power(a, mod - 2);
    }
    void init()
    {
        Pow1[0] = Pow2[0] = invth1[0] = invth2[0] = 1;
        int invp1 = inv(p1), invp2 = inv(p2);
        for (int i = 1; i < N + 5; i++)
        {
            Pow1[i] = 1ll * Pow1[i - 1] * p1 % mod;
            Pow2[i] = 1ll * Pow2[i - 1] * p2 % mod;
            invth1[i] = 1ll * invth1[i - 1] * invp1 % mod;
            invth2[i] = 1ll * invth2[i - 1] * invp2 % mod;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                sum1[i][j] = 1ll * Pow1[i] * Pow2[j] % mod * a[i][j] % mod;
                sum2[i][j] = 1ll * Pow1[n - i + 1] * Pow2[m - j + 1] % mod * a[i][j] % mod;
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                add(sum1[i][j], sum1[i - 1][j]);
                add(sum1[i][j], (sum1[i][j - 1] - sum1[i - 1][j - 1] + mod) % mod);
                add(sum2[i][j], sum2[i - 1][j]);
                add(sum2[i][j], (sum2[i][j - 1] - sum2[i - 1][j - 1] + mod) % mod);
            }
    }
    bool check(int l, int r, int u, int d)
    {
        int g1 = 0;
        add(g1, sum1[u][d]);
        sub(g1, sum1[l - 1][d]);
        sub(g1, sum1[u][r - 1]);
        add(g1, sum1[l - 1][r - 1]);
        int g2 = 0;
        add(g2, sum2[u][d]);
        sub(g2, sum2[l - 1][d]);
        sub(g2, sum2[u][r - 1]);
        add(g2, sum2[l - 1][r - 1]);
        g1 = 1ll * g1 * invth1[l - 1] % mod * invth2[r - 1] % mod;
        g2 = 1ll * g2 * invth1[n - u] % mod * invth2[m - d] % mod;
        return g1 == g2;
    }
};
Hash1 h1;
struct Hash2
{
    const int p1 = 131, p2 = 1331, mod = 1e9 + 9;
    void add(int &x, int y)
    {
        if ((x += y) >= mod)
            x -= mod;
    }
    void sub(int &x, int y)
    {
        if ((x -= y) < 0)
            x += mod;
    }
    int invth1[N + 5], invth2[N + 5];
    int Pow1[N + 5], Pow2[N + 5];
    int sum1[N + 5][N + 5], sum2[N + 5][N + 5];
    int power(int a, int x)
    {
        int ans = 1;
        while (x)
        {
            if (x & 1)
                ans = 1ll * ans * a % mod;
            a = 1ll * a * a % mod;
            x >>= 1;
        }
        return ans;
    }
    int inv(int a)
    {
        return power(a, mod - 2);
    }
    void init()
    {
        Pow1[0] = Pow2[0] = invth1[0] = invth2[0] = 1;
        int invp1 = inv(p1), invp2 = inv(p2);
        for (int i = 1; i < N + 5; i++)
        {
            Pow1[i] = 1ll * Pow1[i - 1] * p1 % mod;
            Pow2[i] = 1ll * Pow2[i - 1] * p2 % mod;
            invth1[i] = 1ll * invth1[i - 1] * invp1 % mod;
            invth2[i] = 1ll * invth2[i - 1] * invp2 % mod;
        }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                sum1[i][j] = 1ll * Pow1[i] * Pow2[j] % mod * a[i][j] % mod;
                sum2[i][j] = 1ll * Pow1[n - i + 1] * Pow2[m - j + 1] % mod * a[i][j] % mod;
            }
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                add(sum1[i][j], sum1[i - 1][j]);
                add(sum1[i][j], (sum1[i][j - 1] - sum1[i - 1][j - 1] + mod) % mod);
                add(sum2[i][j], sum2[i - 1][j]);
                add(sum2[i][j], (sum2[i][j - 1] - sum2[i - 1][j - 1] + mod) % mod);
            }
    }
    bool check(int l, int r, int u, int d)
    {
        int g1 = 0;
        add(g1, sum1[u][d]);
        sub(g1, sum1[l - 1][d]);
        sub(g1, sum1[u][r - 1]);
        add(g1, sum1[l - 1][r - 1]);
        int g2 = 0;
        add(g2, sum2[u][d]);
        sub(g2, sum2[l - 1][d]);
        sub(g2, sum2[u][r - 1]);
        add(g2, sum2[l - 1][r - 1]);
        g1 = 1ll * g1 * invth1[l - 1] % mod * invth2[r - 1] % mod;
        g2 = 1ll * g2 * invth1[n - u] % mod * invth2[m - d] % mod;
        return g1 == g2;
    }
};
Hash2 h2;
bool check(int a, int b, int c, int d)
{
    if (!(a >= 1 && a <= n && b >= 1 && b <= m && c >= 1 && c <= n && d >= 1 && d <= m && a <= c && b <= d))
        return false;
    return h1.check(a, b, c, d) && h2.check(a, b, c, d);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    string s;
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        for (int j = 1; j <= m; j++)
            a[i][j] = s[j - 1] - 'a' + 1;
    }
    h1.init();
    h2.init();
    long long ans = 0;
    for (int z = 1; z <= n; z++)
    {
        int mx = 0, id = 1;
        vector<int> para(m + 1);
        for (int i = 1; i <= m; i++)
        {
            if (mx > i)
                para[i] = min(mx - i, para[2 * id - i]);
            else
                para[i] = 1;
            while (check(z - para[i] + 1, i - para[i] + 1, z + para[i] - 1, i + para[i] - 1))
                para[i]++;
            para[i]--;
            if (para[i] + i > mx)
            {
                mx = para[i] + i;
                id = i;
            }
            ans += para[i];
        }
    }
    for (int z = 1; z < n; z++)
    {
        int mx = 0, id = 1;
        vector<int> para(m + 1);
        for (int i = 1; i < m; i++)
        {
            if (mx > i)
                para[i] = min(mx - i, para[2 * id - i]);
            else
                para[i] = 1;
            while (check(z - para[i] + 1, i - para[i] + 1, z + para[i], i + para[i]))
                para[i]++;
            if (para[i] > 0)
                para[i]--;
            if (para[i] + i > mx)
            {
                mx = para[i] + i;
                id = i;
            }
            ans += para[i];
        }
    }
    cout << ans;
    return 0;
}