Hash水题，枚举每一位然后hash搞一搞
听说自然溢出很快就试了一下
然后就WAWA不休
最后还是回归正常的办法：模大数字（为什么不是质数呢？因为我的两个数字是随便敲的）
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
const long long Mod1=666666666666667ll,Mod2=233333333333333ll;
int n,len,x,ans=0;
long long Ha_F[30005][205],Ha_L[30005][205],tp[30005];
char s[30005][205];
void Get(int x){
for(int i=1;i<=len;i++)Ha_F[x][i]=(Ha_F[x][i-1]*233+s[x][i])%Mod1;
for(int i=len;i;i--)Ha_L[x][i]=(Ha_L[x][i+1]*137+s[x][i])%Mod2;
}
int main(){
freopen("3555.in","r",stdin);
freopen("3555.out","w",stdout);
scanf("%d %d %d",&n,&len,&x);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
Get(i);
}
for(int i=1;i<=len;i++){
for(int j=1;j<=n;j++){
tp[j]=(Ha_F[j][i-1]*Mod2+Ha_L[j][i+1]*Mod1)%(Mod2*Mod1);
}
sort(tp+1,tp+n+1);
int cnt=1;
for(int j=2;j<=n;j++){
if(tp[j]==tp[j-1])ans+=cnt,cnt++;
else cnt=1;
}
}
printf("%d\n",ans);
return 0;
}
评论 (0)
