Sonya and Matrix Beauty CodeForces - 1080E (manacher)-白红宇

Sonya and Matrix Beauty CodeForces - 1080E (manacher)

阅读量：5116 次

发布时间：2019-06-13

本文共 1361 字，大约阅读时间需要 4 分钟。

大意: 给定$nm$字符串矩阵. 若一个子矩形每一行重排后可以满足每行每列都是回文, 那么它为好矩形. 求所有好矩形个数.

一个矩形合法等价于每一行出现次数为奇数的最多只有一个字符, 并且对称的两行对应字符出现次数要完全相等.

那么直接暴力枚举左右边界, 把每个字符的出现次数$hash$一下, 这样就转化为给定序列, 求回文子串个数. 这是manacher算法经典应用, 套板子即可.

暴力计算次数的话$O(26n^3)$竟然没卡过去, 改了好久最后位运算优化到$O(n^3)$才过.

#include 
     
      #include 
      
       #include 
       #include 
        
         #include 
         
          #include 
          
           #define PER(i,a,n) for(int i=n;i>=a;--i)#define REP(i,a,n) for(int i=a;i<=n;++i)#define hr puts("")using namespace std;typedef long long ll;const int N = 1e3+10, P = 998244353; int n, m, rad[N], fac[N];int a[N], b[N], g[N];char s[N][N]; void manacher(int *a, int n) { for (int i=1,j=0,k=-1; i<=n; i+=k) { while (a[i-j-1]==a[i+j+1]) ++j; rad[i] = j; for (k=1; k<=rad[i]&&rad[i-k]!=rad[i]-k; ++k) { rad[i+k] = min(rad[i-k], rad[i]-k); } j = max(j-k, 0); }} int calc(int *a, int n) { if (n<=0) return 0; b[1] = P+1; REP(i,1,n) { b[i*2] = a[i]; b[i*2+1] = P+1; } int ans = n; n = 2*n+1, b[n+1] = P+2; manacher(b,n); REP(i,1,n) ans += rad[i]/2; return ans;} int main() { fac[0] = 1; REP(i,1,30) fac[i] = fac[i-1]*991ll%P; scanf("%d%d", &n, &m); REP(i,1,n) scanf("%s",s[i]+1); ll ans = 0; REP(L,1,m) { REP(i,0,n) a[i] = g[i] = 0; REP(R,L,m) { int now = 0; REP(i,1,n) { a[i] = (a[i]+fac[s[i][R]-'a'])%P; g[i] ^= 1<

转载于:https://www.cnblogs.com/uid001/p/11312620.html

你可能感兴趣的文章