字符串

Hash

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e5 + 9;
const ll mod = 100001333;
const ll P = 131;
ull Hash[N];
ull pp[N];
ll getlen(ll a, vector<ll> &v) {
    ll ret = 0;
    while (a) {
        ret++;
        v.push_back(a % 2);
        a /= 2;
    }
    return ret;
}
char str[N];
map<ull, int>mp;
void solve() {
    int t, m;
    cin >> t ;
    int ans = 0;
    while (t--) {
        cin >> (str + 1);
        Hash[0] = 0;
        ull p = P;
        pp[0] = 1;
        int n = strlen(str + 1);
        for (int i = 1; i <= n; i++) {
            pp[i] = pp[i - 1] * P;
            Hash[i] = Hash[i - 1] * p + str[i];
        }
        if (!mp.count(Hash[n])) {
            ans++;
            mp[Hash[n]] = 1;
        } 
    }cout << ans << endl;
}
signed main() {
    ll t = 1;  // cin >> t;
    while (t--) {
        solve();
    }
}

由于单 (hash) 太容易被卡了，所以模数不要简单地自然溢出，要用 (100001333) 等不会被卡的模数。