查了半天终于懂了:
在get_hash是如果传入的k(也就是get_sum(str))过大的话,k会超出long long的范围,变成负数,要判断一下。
就像这样:
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int M = 23333;
int n, cnt = 0;
string linker[M + 3];
LL get_num(string str)
{
LL base = 3, len = str.length(), hash = 0;
for(LL i = 0; i < len; i ++)
{
hash = (hash + 29 + int(str[i]) * base) % M;
base *= 3;
// 就是这里!!!
if(hash < 0) hash += M;
}
return hash;
}
int h1(int k)
{ return (k + 2) % M + 7; }
int h2(int k)
{ return k % M + 3; }
int get_hash(int k)
{
int hash = 0;
for(int i = 0; i <= M; i ++)
{
hash = (h1(k) + i * h2(k)) % M;
if(!linker[hash].size()) return hash;
}
return 0;
}
void insert(string key)
{ linker[get_hash(get_num(key) % M)] = key; }
int find(string str)
{
int k = get_num(str) % M, hash = 0;
for(int i = 0; i <= M; i ++)
{
hash = (h1(k) + i * h2(k)) % M;
if(linker[hash] == str) return 1;
else if(!linker[hash].length()) return 0;
}
return 0;
}
int main()
{
scanf("%d", &n);
while(n --)
{
string str;
cin >> str;
if(!find(str))
{
cnt ++;
insert(str);
}
}
printf("%d", cnt);
return 0;
}
```
by ZYK_luogu @ 2023-12-03 16:39:01
@[ZYK_luogu](/user/742157) 其实你可以用unsigned long long自然溢出来哈希
by _H17_ @ 2024-02-09 11:15:21