LA 6047 Perfect Matching 字符串哈希

一开始我用的Trie+计数，但是不是计多了就是计少了，后来暴力暴过去的……

看了别人的代码知道是字符串哈希，但是仍有几个地方不理解：

1.26^500溢出问题

2.没考虑哈希碰撞？

跪求指点！

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 #define LL unsigned long long int
 6 
 7 const int MAXN = 1010;
 8 const int MAXLEN = 510;
 9 
10 int N;
11 char str[MAXN][MAXLEN];
12 int len[MAXN];
13 LL Hash[MAXN];      //原串哈希值
14 LL reHash[MAXN];    //逆转串哈希值
15 LL fac[MAXLEN];
16 
17 void init()
18 {
19     fac[0] = 1;
20     for ( int i = 1; i < MAXLEN; ++i )
21         fac[i] = fac[i - 1] * 26;
22     return;
23 }
24 
25 void chuli( int id )
26 {
27     len[id] = strlen( str[id] + 1 );
28     Hash[id] = 0;
29     for ( int i = 1; i <= len[id]; ++i )
30         Hash[id] = Hash[id] * 26 + str[id][i] - 'a';
31 
32     reHash[id] = 0;
33     for ( int i = len[id]; i > 0; --i )
34         reHash[id] = reHash[id] * 26 + str[id][i] - 'a';
35 
36     return;
37 }
38 
39 int main()
40 {
41     int T, cas = 0;
42     init();
43     scanf( "%d", &T );
44     while ( T-- )
45     {
46         scanf( "%d", &N );
47         for ( int i = 0; i < N; ++i )
48         {
49             scanf("%s", str[i] + 1 );
50             chuli( i );
51         }
52 
53         int ans = 0;
54         for ( int i = 0; i < N; ++i )
55             for ( int j = 0; j < N; ++j )
56             {
57                 if ( i == j ) continue;
58                 if ( Hash[i] * fac[ len[j] ] + Hash[j] == reHash[j] * fac[ len[i] ] + reHash[i] )
59                     ++ans;
60             }
61 
62         printf( "Case #%d: %d
", ++cas, ans );
63     }
64     return 0;
65 }