牛客9510D - 数列

• 链接：https://ac.nowcoder.com/acm/contest/9510/D
• 知识点：取模的性质、哈希
• 难度：蓝

题意

给出一个数列，求有多少个区间里每个数都出现了 $KK$ 的倍数次。

思路

往 $\mathrm{\%}K\backslash \%\; K$ 的方向考虑

• 原因：涉及到倍数次都往这方面想。
• 如果你对这个性质不熟，推荐你用这些题练手：牛客91L、牛客14694、洛谷2634

接着，按照感觉，考虑 DP。 我们马上发现，DP很难，因为他要求“每个数都出现了 K 的倍数次”。 我们发现，他要求的是连续的区间，不是子序列。 哈希能够压缩状态，并且我们对一个序列求哈希后，如果后来要修改序列中的某个数字，可以 $O(1)O(1)$ 地修改。 序列就是 $\{a_1\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{次}\mathrm{数}\mathrm{\%}K,a_2\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{次}\mathrm{数}\mathrm{\%}K,\mathrm{.}\mathrm{.}\mathrm{.}{a}_n\mathrm{出}\mathrm{现}\mathrm{的}\mathrm{次}\mathrm{数}\mathrm{\%}K\}\backslash lbrace\; a\_1出现的次数\backslash \%K,a\_2出现的次数\backslash \%K,...a\_n出现的次数\backslash \%K\backslash rbrace$ 具体就是： map<序列的哈希, 该哈希出现的次数> 怎么累加答案呢？ 略。

代码

#include <cstdio>
#include <iostream>
#include <map>
#define int long long
const int N		= 1e6+10;
const int MOD	= 1e9+7;
const int BASE1 = 131;
const int BASE2 = 1331;
using namespace std;


long long POW(long long a,long long b)
{
	long long ans=1;
	while(b>0)
	{
		if(b&1)
		{
			ans*=a;
			ans%=MOD;
		}
		a*=a;
		a%=MOD;
		b>>=1;
	}
	
	return ans;
}


int UPD(int pre_hash,int pos,int new_val,int pre_val,int base)
{
	int tmp = POW(base, pos-1);
	return pre_hash - pre_val * tmp + new_val * tmp;
}

map< pair<int,int> , int> mp;
int arr[N];
int sumi[N];
int n, K;

void Solve()
{
	mp[{0,0}] = 1;
	int hash1 = 0, hash2 = 0;
	int ans = 0;
	for (int i=1; i<=n; i++)
	{
		int pre = sumi[ arr[i] ];
		sumi[ arr[i] ]++, sumi[ arr[i] ] %= K;
		int cur = sumi[ arr[i] ];
		hash1 = UPD(hash1, arr[i], cur, pre, BASE1);
		hash2 = UPD(hash2, arr[i], cur, pre, BASE2);
		
		ans += mp[ {hash1,hash2} ];
		
		mp[ {hash1,hash2} ]++;
		
	}
	
	printf("%lld\n",ans);
}


signed main()
{
	scanf("%lld %lld",&n,&K);
	for (int i=1; i<=n; i++)
	{
		scanf("%lld",&arr[i]);
	}
	Solve();
	
	return 0;
}