牛客挑战赛46 D （哈希、随机数）

[题目链接](https://ac.nowcoder.com/acm/contest/9510/D) ------------ 维护前缀哈希值$\sum hash[x]*cnt[x]$，其中$cnt[x]$为$x$在模域$k$出现的次数 ------------ ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; const int M=1e6+5; auto random_address = [] { char *p = new char; delete p; return uint64_t(p); }; const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1); mt19937_64 rng(SEED); unordered_map<ull,int> mp; int cnt[M]; ull val[M]; int main() { int n,k;scanf("%d%d",&n,&k); ll ans=0; ull haxi=0; mp[0]=1; for(int i=1;i<=n;i++) { int x;scanf("%d",&x); if(!val[x])val[x]=rng(); ull tmp=val[x]; haxi-=cnt[x]*tmp; cnt[x]=(cnt[x]+1)%k; haxi+=cnt[x]*tmp; ans+=mp[haxi]; mp[haxi]++; } printf("%lld\n",ans); return 0; } ```