origami_ANDR

#include <bits/stdc++.h>

using namespace std;
ifstream fin("origami.in");
ofstream fout("origami.out");

vector<string> arr, aux;
string str;
vector<int> dp[4], mnm[4], Long;

void findLongest(int n)
{
    Long.resize(n+1);
    for(int i=1, m=0, l=0, r=0; i<=n; i++)
    {
        if(i>r)
        {
            Long[i]=1;
            l=r=m=i;
            while(l>1 && r<n && str[l-1]==str[r + 1])
            {
                Long[i]++;
                l--;
                r++;
            }
        }
        else
        {
            int p=m-(i-m);
            if(p-Long[p]+1>l)
                Long[i]=Long[p];
            else
            {
                Long[i]=p-l+1;
                l=i-Long[i]+1;
                m=i;
                while(l>1 && r<n && str[l-1]==str[r + 1])
                {
                    Long[i]++;
                    l--;
                    r++;
                }
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(str[i-Long[i]+1]=='#')
            Long[i]--;

        Long[i]=(Long[i]+(i%2))/2;

    }
    return;
}

int main()
{
    int n, m;
    fin>>n>>m;
    arr.resize(n);
    for(string &axs : arr)
        fin>>axs;
    for(int k=0; k<=3; k++)
    {
        mnm[k].assign(n, numeric_limits<int> :: max());
        dp[k].resize(n);
        str.resize(n*2);
        dp[k][0]=1;
        for(int i=0; i<=n*2-1; i++)
            str[i]='#';
        for(int j=0; j<=m-1; j++ )
        {
            for(int i=0, t=1; i<=n-1; i++, t+= 2)
                str[t] = arr[i][j];
            findLongest(n*2-1);
            for(int i=1; i<=n-1; i++ )
                mnm[k][i]=min(mnm[k][i], Long[i*2]);
        }
        for(int i=1; i<=n-1; i++)
            dp[k][i]=dp[k][i-1]+(dp[k][i-1]-((i-mnm[k][i]-1<0) ? 0 : dp[k][i-mnm[k][i]-1])>=1);
        aux.resize(m);
        for(string &axs : aux)
            axs.clear();
        for(int i=n-1; i>=0; i--)
            for(int j=0; j<=m-1; j++)
                aux[j].push_back(arr[i][j]);
        swap(n,m);
        arr=aux;
        if(k>=2)
        {
            reverse(dp[k].begin(), dp[k].end());
            reverse(mnm[k].begin(), mnm[k].end());
        }
    }
    long long sol=0;
    for(int i=0; i<=n-1; i++)
        for(int j=0; j<=m-1; j++)
            if((i==0 || dp[0][i]-dp[0][i-1]==1) && (j==0 || dp[1][j]-dp[1][j-1]==1))
                sol +=dp[2][i]*dp[3][j];
    fout<<sol<<'\n';
    return 0;

}