1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
| #include<bits/stdc++.h>
#define REG register
using namespace std;
inline void read(int& x){
REG char c;
while(!isdigit(c=getchar()));x=c^48;
while(isdigit(c=getchar()))x=(x*10)+(c^48);
}
const int S=26,N=505;
int n,m;
char str[N][N];
int Ans;
short PreV[N][N][S];
inline void Pre_Init(){
for(REG int i=1;i<=n;++i)
for(REG int j=1;j<=m;++j){
for(REG int c=0;c<S;++c) PreV[i][j][c]=PreV[i][j-1][c];
++PreV[i][j][str[i][j]-'a'];
}
}
inline void GetV(int i,int l,int r,short* V){for(REG int c=0;c<S;++c)V[c]=PreV[i][r][c]-PreV[i][l-1][c];}
inline bool cmp(short* V1,short* V2){
for(REG int c=0;c<S;++c)
if(V1[c]^V2[c]) return false;
return true;
}
inline bool cmp(short* V){
int cnt=0;
for(REG int c=0;c<S;++c) cnt+=(V[c]&1);
return cnt<=1;
}
short Vtmp1[N][S],MxR,MxC,MRad[N];
inline void Manacher(int l,int r){
for(REG int i=1;i<=n;++i) GetV(i,l,r,Vtmp1[i<<1]);
MxR=MxC=0;
for(REG int i=1;i<=2*n+1;++i){
int ML=i>MxR?1:min(MRad[2*MxC-i],(short)(MxR-i+1));
while((i-ML)&&(i+ML<=2*n+1))
if(cmp(Vtmp1[i-ML],Vtmp1[i+ML])) ++ML;
else break;
MRad[i]=ML;
if(i+ML-1>MxR) MxR=i+ML-1,MxC=i;
}
}
short UMD[N],DMD[N];
inline void UD(int l,int r){
for(REG int i=1;i<=n;++i) UMD[i]=0,DMD[i]=n+1;
int lst=0;
for(REG int i=1;i<=n;++i){
if(cmp(Vtmp1[i<<1])) UMD[i]=lst;
else
for(UMD[i]=DMD[i]=i,++lst;lst<i;++lst) DMD[lst]=i;
}
}
inline void Work(){
read(n),read(m);
for(REG int i=1;i<=n;++i) scanf("%s",str[i]+1);
Pre_Init();
for(REG int l=1;l<=m;++l)
for(REG int r=l;r<=m;++r){
Manacher(l,r),UD(l,r);
for(REG int i=2;i<=2*n;++i){
if(i&1){
int U=min((i-1)/2-UMD[(i-1)>>1],MRad[i]>>1);
int D=min(DMD[(i+1)>>1]-(i+1)/2,MRad[i]>>1);
Ans+=min(U,D);
}
else{
int U=min(i/2-UMD[i>>1],MRad[i]>>1);
int D=min(DMD[i>>1]-i/2,MRad[i]>>1);
Ans+=min(U,D);
}
}
}
printf("%d\n",Ans);
}
int main(){Work();}
|
