【题解】Sonya and Matrix Beauty [Codeforces1080E]

传送门：\(Sonya\) \(and\) \(Matrix\) \(Beauty\) \([CF1080E]\)

【题目描述】

\(Sonya\) 最近过了生日，她收到一个 \(n \times m\) 的字符矩阵。

我们称一个子矩阵是美丽的，当且仅当在重新排列这个子矩阵每一行的字符后，使得这个子矩阵的每一行每一列都是回文串。

\(Sonya\) 想要知道这个矩阵中有几个子矩阵是美丽的。

（给定一个 \(n \times m\) 的字符矩阵，求有多少个子矩阵在任意排列每一行内的字符后，使得子矩阵的每行每列都是回文串）

【样例】

样例输入：

1 3

aba

样例输出：

4

样例输入：

2 3

aca

aac

样例输出：

11

样例输入：

3 5

accac

aaaba

cccaa

样例输出：

43

【数据范围】

\(100\%\) \(1 \leqslant n,m \leqslant 250\)

【分析】

先膜一膜隔壁大佬 \(Hash\) 判回文的方法，一脸懵逼的本蒟蒻只能另找出路了。。。

由于每一行的以内的字符可以任意排列，子矩阵中的某一行字符可以形成回文串，当且仅当该行中出现次数为奇数的字符只有一个。

如果让每一列都形成回文串的话，那么关于中心行对称的任意两行都应是完全相同的，否则就无法做到每一列都一样。

将子矩阵每一行视为一个字符，比较两个字符（行）是否相等时就看其 \(26\) 个字母的个数是否全部相同，对于内部本身无法形成回文的字符（行）就不让它与其他的匹配。

枚举一下子矩阵的左右边界，然后处理出 \(26\) 个字母在子矩阵每一行中分别出现的次数，然后对这 \(n\) 个字符（行）跑一遍 \(Manacher\) 得到上下边界，最后答案取个最大值就 \(ok\) 啦！

时间复杂度：\(O(nm^2)\) 。

【Code】

#include<cstdio>

#define Re register int

const int N=510;

int n,m,a,p,q,Ans,f[N],odd[N],cnt[N][30];char ch[N][N];

inline int min(Re a,Re b){return a<b?a:b;}

inline bool cmp(Re a,Re b){

    if(odd[a]>1||odd[b]>1)return 0;//本身不能形成回文的统统踢掉

    for(Re i=0;i<26;++i)if(cnt[a][i]!=cnt[b][i])return 0;

    return 1;

}

int main(){

    scanf("%d%d",&n,&m);

    for(Re i=1;i<=n;++i)scanf("%s",ch[i]+1);

    for(Re L=1;L<=m;++L){

    	for(Re i=0;i<=n;odd[2*i-1]=0,++i)

            for(Re j=0;j<26;++j)

            	cnt[2*i-1][j]=0;//初始化

    	for(Re R=L;R<=m;++R){

            for(Re i=1;i<=n;++i){//右边界从前往后扫，每次都只需要处理n个新加进来的字符

            	++cnt[2*i-1][a=ch[i][R]-'a'];

            	if(cnt[2*i-1][a]&1)++odd[2*i-1];

            	else --odd[2*i-1];

            }

            for(Re i=0;i<=2*n;++i)f[i]=0;//回文半径的初始化

            cnt[2*n+1][0]=-1;//防止多余的部分被匹配

            p=q=0;

            for(Re i=1;i<=2*n;++i){

                if(odd[i]>1)continue;//自身都不符合要求，还想找配偶？没门！

            	f[i]=q>i?min(f[(p<<1)-i],q-i):1;

            	while(cmp(i-f[i],i+f[i])==1)++f[i];

            	if(i+f[i]>q)q=(p=i)+f[i];

            	Ans+=f[i]/2;//因为之前在字符（行）序列中加入了空位置，所以统计答案时要除2

            }

    	}

    }

    printf("%d",Ans);

}