题目链接:
查询有多少\([l,r]\)区间满足每个数出现\(k\)的倍数次
即为\(1\)到\(r\)与\(1\)到\(l-1\)每个数相减的次数为\(k\)的倍数次
可以使用哈希维护
记录每个数出现的次数为\(cnt[x]\),哈希值为\(hash[x]\)
那么前缀哈希和即为\(\sum_{x} cnt[x]*hash[x]\)(\(cnt\)注意要模\(k\))
当我们循环到i时候,更新哈希值,查询得到的哈希值在之前map[hash]出现的次数
(\([l,r]\)区间的哈希值为0)
就可以得到以\(i\)结尾的符合条件区间的个数,从而得到答案
#include <bits/stdc++.h>
#define LL long long
#define ull unsigned long long
using namespace std;
const int N = 1e6 + 101;
int n, k;
int a[N];
ull hash[N], cnt[N], now;
map<ull,int>mp;
ull rnd() { return (ull)rand() * (ull) rand() * (ull) rand(); }
signed main()
{
srand(time(0));
scanf("%d%d",&n,&k);
for(int i = 1;i <= n; i++) hash[i] = rnd();
for(int i = 1;i <= n; i++) scanf("%d",&a[i]);
mp[0] ++;LL ans = 0;
for(int i = 1;i <= n; i++)
{
int x = a[i];
now -= cnt[x] * hash[x];
cnt[x] = (cnt[x] + 1) % k;
now += cnt[x] * hash[x];
ans += mp[now];
mp[now] ++;
}
cout << ans << endl;
}