问题 L: Rem of Sum is Num--------------------------------思维(套路题)

题目描述
Given are a sequence of N positive integers A1,A2,…,AN, and a positive integer K.
Find the number of non-empty contiguous subsequences in A such that the remainder when dividing the sum of its elements by K is equal to the number of its elements. We consider two subsequences different if they are taken from different positions, even if they are equal sequences.

Constraints
·All values in input are integers.
·1≤N≤2×105
·1≤K≤109
·1≤Ai≤109

输入
Input is given from Standard Input in the following format:

N K
A1 A2 ⋯ AN

输出
Print the number of subsequences that satisfy the condition.

样例输入 Copy
【样例1】
5 4
1 4 2 3 5
【样例2】
8 4
4 2 4 2 4 2 4 2
【样例3】
10 7
14 15 92 65 35 89 79 32 38 46
样例输出 Copy
【样例1】
4
【样例2】
7
【样例3】
8
提示
样例1解释
Four sequences satisfy the condition: (1), (4,2), (1,4,2), and (5).
样例2解释
(4,2) is counted four times, and (2,4) is counted three times.

解析:

1.(s[r]-s[l])%k=(r-l)
2.s[r]-s[l]=k*m+(r-l) //左边去掉了k倍，相当于右边加了k倍
3.(s[r]-r)-(s[l]-l)=k*m
4.(s[r]-r)%k-(s[l]-l)%k==0
5.s[r]-r=s[l]-l;

假设f(x)=s[x]-x; 所以我们只要预处理f(x)然后在统计出现的次数。
但是题目有要求区间长度要<m。
所以转化成 区间长度<m.相同f(x)出现的次数之和

对于[m,n]这段区间，就像滑动窗口一样，我们要把前面的产生的贡献减去。再计算和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10000; 
ll a[N];
ll sum[N]; 
map<ll,ll> v;
int n,k;
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++)
	{
		sum[i]=(sum[i]-i+k)%k;
	}
	ll low=min(k-1,n);
	ll res=0;
	for(int i=0;i<=low;i++)
	{
		res+=v[sum[i]];
		v[sum[i]]++;
	}
	for(int i=low+1;i<=n;i++)
	{
		v[sum[i-k]]--;
		res+=v[sum[i]];
		v[sum[i]]++;
	}
	cout<<res<<endl;
 }