rt，本地测试250x250的全a方阵可以在0.7s跑出结果但是CF直接TLE

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

const int N = 510, M1 = 20080113, M2 = 20070912, P = 13331, mod = 998244353;
char a[N][N];
ll Hash[N][N];
ll t[N], s[N << 2];
bool ok[N];
int f[N << 2];
ll p[N]; 
int cnt[N][N][26], idx;
ll ans;
int n, m, len;
inline int add(int x,int y)
{
    if(x+y>mod) return x+y-mod;
    return x+y;
}
inline ll gethash(int k, int l, int r)
{
    int cntt = 0;
    ll res = 0;
    for(register int i = 0; i < 26; i ++ )
    {
        int cnti = cnt[k][r][i] - cnt[k][l - 1][i];
        if(cnti & 1) cntt ++;
        res = add(res * P%mod,cnti);
    }
    if(cntt <= 1) ok[k] = true;
    return res;
}

inline void init()
{
    len = 0;
    s[++ len] = M1;
    for(register int i = 1; i <= n; i ++ )
    {
        if(ok[i])
            s[++ len] = t[i];
        else s[++ len] = idx --;
        s[++ len] = M1;
    }
}

inline int manacher(int len)
{
    for(int i=0;i<=len;i++) f[i]=0;
    int mid = 0, r = 0;
    for(register int i = 1; i <= len; i ++ )
    {
        if(s[i] < 0) continue;
        if(i <= r) f[i] = min(f[2 * mid - i], r - i + 1);
        while(s[i + f[i]] == s[i - f[i]] && i - f[i] >= 1 && i + f[i] <= len) 
            f[i] ++;
        if(i + f[i] > r) r = i + f[i] - 1, mid = i;
    }
    int ans = 0;
    for(int i = 1; i <= len; i ++ ) ans += f[i] / 2;
    return ans;
}

int main()
{
    #ifdef LOCAL
        freopen("D:\\workspace\\in_and_out\\in.in", "r", stdin);
        freopen("D:\\workspace\\in_and_out\\out.out", "w", stdout);
    #endif

    double st = clock();

    n = read(), m = read();
    for(register int i = 1; i <= n; i ++ ) scanf("%s", a[i] + 1);
    p[0] = 1;
    for(register int i = 1; i < N - 5; i ++ ) p[i] = p[i - 1] * P % mod;

    for(register int i = 1; i <= n; i ++ )
        for(register int j = 1; j <= m; j ++ )
        {
            for(register int k = 0; k < 26; k ++ )
                cnt[i][j][k] = cnt[i][j - 1][k];
            cnt[i][j][a[i][j] - 'a'] ++;
        }
    
    for(register int L = 1; L <= m; L ++ )
    {
        for(register int R = L; R <= m; R ++ )
        {
            idx = -5;
            for(int k=1;k<=n;k++) ok[k]=false;
            for(register int k = 1; k <= n; k ++ )
                t[k] = gethash(k, L, R);
            init();
            ans += manacher(len);
        }
    }

    cout << ans << endl;
    // cout << (clock() - st) / CLOCKS_PER_SEC << endl;

    return 0;
}