BZOJ 3555 [Ctsc2014]企鹅QQ(hash)

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cstdio>
 5 #include<algorithm>
 6 using namespace std; 
 7 int n,l,k,ans;
 8 unsigned long long hash[30010][210],hash1[210][30010],pw[5000],ma[2000];;
 9 char s[50010];
10 int main(){
11     scanf("%d%d%d",&n,&l,&k);
12     ma[‘0‘]=64;ma[‘1‘]=1;ma[‘2‘]=2;ma[‘3‘]=3;ma[‘4‘]=4;ma[‘5‘]=5;ma[‘6‘]=6;ma[‘7‘]=7;
13     ma[‘8‘]=8;ma[‘9‘]=9;ma[‘A‘]=10;ma[‘B‘]=11;ma[‘C‘]=12;ma[‘D‘]=13;ma[‘E‘]=14;ma[‘F‘]=15;
14     ma[‘G‘]=16;ma[‘H‘]=17;ma[‘I‘]=18;ma[‘J‘]=19;ma[‘K‘]=20;ma[‘L‘]=21;ma[‘M‘]=22;ma[‘N‘]=23;
15     ma[‘O‘]=24;ma[‘P‘]=25;ma[‘Q‘]=26;ma[‘R‘]=27;ma[‘S‘]=28;ma[‘T‘]=29;ma[‘U‘]=30;ma[‘V‘]=31;
16     ma[‘W‘]=32;ma[‘X‘]=33;ma[‘Y‘]=34;ma[‘Z‘]=35;ma[‘a‘]=36;ma[‘b‘]=37;ma[‘c‘]=38;ma[‘d‘]=39;
17     ma[‘e‘]=40;ma[‘f‘]=41;ma[‘g‘]=42;ma[‘h‘]=43;ma[‘i‘]=44;ma[‘j‘]=45;ma[‘k‘]=46;ma[‘l‘]=47;
18     ma[‘m‘]=48;ma[‘n‘]=49;ma[‘o‘]=50;ma[‘p‘]=51;ma[‘q‘]=52;ma[‘r‘]=53;ma[‘s‘]=54;ma[‘t‘]=55;
19     ma[‘u‘]=56;ma[‘v‘]=57;ma[‘w‘]=58;ma[‘x‘]=59;ma[‘y‘]=60;ma[‘z‘]=61;ma[‘_‘]=62;ma[‘@‘]=63;
20     pw[0]=1;
21     for(int i=1;i<=l;i++){
22         pw[i]=pw[i-1]*65;
23     }
24     for(int i=1;i<=n;i++){
25         scanf("%s",s+1);
26         for(int j=1;j<=l;j++){
27             hash[i][j]=hash[i][j-1]*65+ma[s[j]];
28         } 
29         for(int j=1;j<=l;j++){
30             hash1[j][i]=hash[i][j-1]*pw[l-j]+hash[i][l]-hash[i][j]*pw[l-j];
31         }
32     }
33     for(int i=1;i<=l;i++){
34         sort(hash1[i]+1,hash1[i]+1+n);
35         int cnt=0;
36         for(int j=1;j<=n;j++){
37             if(hash1[i][j]!=hash1[i][j-1])cnt=1;
38             else {
39                 ans+=cnt;
40                 cnt++;
41             }
42         }
43     }
44     printf("%d\n",ans);
45     return 0;
46 }