「AtCoder abc146E」Rem of Sum is Num

题意：给一个长为 $n$ 的数列 $A$ 和一个整数 $k$，判断数列有多少个子序列满足子序列的和除以 $k$ 的余数与其数的个数相同。

由题知，题目要我们求满足以下条件的个数：

$$sum[i]-sum[j]\equiv i-j\mod k\ (1\le j<i\le n)$$

简单化简一下便可轻松的得到以下式子：

$$sum[i]-i\equiv sum[j]-j\mod k\ (1\le j<i\le n)$$

所以我们新建立一个数组 $num[i]$ 代表 $(sum[i]-i)\mod k$ ，由于一定要满足 $i-j<=k$ (否则取余后肯定没有这么大)，所以就是查询一段长度小于 $k$ 的区间中，相同 $num$ 的对数。

可以选择 multiset 或 map 两种方式维护。

Multiset($70$ pts)

直接每次加上 count 值再 insert 即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=2e6+100;
int n,k,a[maxn],ans;
long long num[maxn],sum[maxn];
multiset<int> p;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		sum[i]=sum[i-1]+a[i];
		num[i]=(sum[i]-i+k)%k;
	}
	p.insert(0);
	for(int i=1;i<=n;i++)
	{
		if(i>=k)
			p.erase(p.find(num[i-k]));
		ans+=p.count(num[i]);
		p.insert(num[i]);
	}
	printf("%d",ans);
	return 0;
}

Map($100$ pts)

直接先预处理好 $0\sim k-1$ 之间的答案，以后每次把这个区间向右移动一个，将 map[i]++,map[i-k]--。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
const int maxn=2e6+100;
long long n,k,a[maxn],ans;
long long num[maxn],sum[maxn];
map<long long,int> p;
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum[i]=sum[i-1]+a[i];
		num[i]=(sum[i]-i+k)%k;
	}
	int m=min(k-1,n);
	for(int i=0;i<=m;i++)
	{
		ans+=p[num[i]];
		p[num[i]]++;
	}
	for(int i=m+1;i<=n;i++)
	{
		p[num[i-k]]--;
		ans+=p[num[i]];
		p[num[i]]++;
	}
	printf("%lld",ans);
	return 0;
}