C++14(g++5.4) 解法, 执行用时: 203ms, 内存消耗: 10212K, 提交时间: 2019-05-31 21:47:17

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100005;
map<int,int>m;
int k,b,n,a[maxn];
int main()
{
	cin>>k>>b>>n;
	for(int i=1;i<=n;i++)
        cin>>a[i];
	ll ans=0;
	for(int i=1,pre=1;i<=n;i++)
	{
		if(a[i])pre=i+1;
		else ans+=i-pre+1;
	}
	if(b==0)
	{
		cout<<ans<<endl;
		return 0;
	}
	if(b==k-1)ans=-ans,b=0;
	else ans=0;
	m[0]=1;
	for(int i=1,res=0;i<=n;i++)
	{
		res=(res+a[i])%(k-1);
		ans+=m[(res-b+k-1)%(k-1)];
		m[res]+=1;
	}
	cout<<ans<<endl;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 128ms, 内存消耗: 14512K, 提交时间: 2023-07-19 15:43:36

 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll k,b,n,a[N],s[N];
map<ll,ll>m;
int main()
{
	cin>>k>>b>>n;
	ll res=0,z=0,t=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=(s[i-1]+a[i])%(k-1);
		if(a[i]==0)
			t++,z+=t;
		else
			t=0;
	}
	if(b==0)
	{
		cout<<z;
		return 0;
	}
	m[0]++;
	for(int i=1;i<=n;i++)
	{
		ll val=(s[i]-b+k-1)%(k-1);
		res+=m[val];
		m[s[i]]++;
	}
	if(b==k-1)
		res-=z;
	cout<<res;
	return 0;
}