牛客挑战赛46 D

题目链接：

数列

查询有多少\([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;

}

巴特西

牛客挑战赛46 D

题目链接：

最新文章

热门文章