CodeForces 1080E - Sonya and Matrix Beauty

· · 题解

洛谷题目页面传送门 & CodeForces题目页面传送门

若一个矩阵满足存在一种重新排列每行的方案，使得排列之后的每行每列都是回文串，那么称它是美丽的。给定一个n\times m的字符矩阵a，求有多少个美丽子矩阵。

考虑探索一个矩阵美丽的充要条件。

某行能够重排之后变成回文串，显然当且仅当这行出现次数为奇数的字符的数量\leq1。充分性和必要性都很显然。

接下来考虑每列都回文的充要条件。显然，重排每行之后能够每列都回文，当且仅当重排之后能够从上到下每行的字符串组成的字符串序列回文，显然又等价于从上到下每行的字符多重集组成的多重集序列回文。这个字符多重集可以用一个|\Sigma|元组表示，第i个元素表示第i种字符出现的次数。

这样一来，我们显然可以枚举子矩阵的起始列、终止列，就转化成了\mathrm O\!\left(m^2\right)个回文子串计数问题。对于每一次枚举，我们算出每一行的表示字符多重集的|\Sigma|元组，然后跑Manacher即可。

然鹅这一次Manacher与正常的稍有不同。对于每一次枚举，因为有可能有的行不满足“这行出现次数为奇数的字符的数量\leq1”，它内部不能组成回文串，所以要跑Manacher的字符串中会有不可匹配的“字符”（|\Sigma|元组）出现。这怎么办呢？不妨定义一个新的可匹配函数eq:eq(x,y)=[x=y\land odd_x\leq1\land odd_y\leq 1]，其中odd_x表示字符多重集x中出现次数为奇数的字符数量。这样，eq显然不满足自反性，但是满足传递性。注意：Manacher算法不需要自反性，只需要传递性。所以Manacher可以照常跑。

至于|\Sigma|元组们和odd数组如何快速求出，枚举过程中递推即可。

时间复杂度\mathrm O\!\left(nm^2|\Sigma|\right)。可能会被卡常哟！怎么做到保证不被卡常呢？可以用集合哈希去哈希|\Sigma|元组，使得判断2个|\Sigma|元组相等只需\mathrm O(1)，并且哈希值也可以递推。这样时间复杂度是\mathrm O\!\left(nm^2\right)的。不过本蒟蒻没有被卡常，就不写哈希了吧！

下面是AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=250,M=250,LET=26;
int n/*行数*/,m/*列数*/;
char a[N+1][M+5];//字符矩阵 
vector<int> cnt[N+1];//|Σ|元组 
int odd[N+1];//odd[i]表示cnt[i]中奇数的数量 
int s;//|b|
vector<int> b[2*N+2];//塞上分隔符之后的|Σ|元组序列 
bool ok[2*N+2];//ok[i]表示b[i]能否行内回文 
void sep(){//塞分隔符（分隔符是vector<int>(LET,0)） 
    b[s=1]=vector<int>(LET,0);ok[s]=true;//分隔符自然可匹配 
    for(int i=1;i<=n;i++)b[++s]=cnt[i],ok[s]=odd[i]<=1,b[++s]=vector<int>(LET,0),ok[s]=true;
}
bool eq(int x,int y){return ok[x]&&ok[y]&&b[x]==b[y];}//可匹配函数 
int rds[2*N+2];//最长回文半径数组 
void manacher(){//对b跑Manacher算法 
    int mid=0,r=0;
    for(int i=1;i<=s;i++)
        if(r<i){
            rds[i]=0;
            while(i-rds[i]>=1&&i+rds[i]<=s&&eq(i-rds[i],i+rds[i])/*调用可匹配函数*/)rds[i]++;
            mid=i;r=i+rds[i]-1;
        }
        else if(i+rds[2*mid-i]<=r)rds[i]=rds[2*mid-i];
        else{
            rds[i]=r-i+1;
            while(i-rds[i]>=1&&i+rds[i]<=s&&eq(i-rds[i],i+rds[i])/*调用可匹配函数*/)rds[i]++;
            mid=i;r=i+rds[i]-1;
        }
}
signed main(){
//  freopen("C:\\Users\\chenx\\OneDrive\\桌面\\data.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i]+1;
    for(int i=1;i<=n;i++)cnt[i].resize(LET);
    int ans=0;
    for(int i=1;i<=m;i++){//枚举起始列 
        for(int j=1;j<=n;j++){//新一轮递推，清空数据 
            for(int k=0;k<LET;k++)cnt[j][k]=0;
            odd[j]=0;
        } 
        for(int j=i;j<=m;j++){//枚举终止列 
            for(int k=1;k<=n;k++)odd[k]+=++cnt[k][a[k][j]-'a']&1?1:-1;//递推求odd,cnt 
            sep();//塞分隔符 
            manacher();//对b跑Manacher 
            for(int k=1;k<=2*n+1;k++)ans+=rds[k]>>1;//贡献答案 
        }
    }
    cout<<ans;
    return 0;
}