题目

做法

\((x)_k\)定义编号，如果\(a+b\)加到一起能进一位，\(a+b\rightarrow 1+(a+b-k)=a+b-(k-1)\)，故\(d(a_{l,r})=\sum\limits_{i=l}^r a_i\% k-1\)

但我们发现\(k-1\)这一块缺失了，显然为\(0\)当且仅当区间均为\(0\)，其他情况得出\(0\)的时候实际结果为\(k-1\)

• \(b=0\)：全\(0\)区间个数

• \(b=k-1\)：满足\(/%(k-1)=0\)的个数-全\(0\)区间个数

• 其他情况：\(a_{l,r}=sum_r-sum_{l-1}\%(k-1),sum_r-sum_{l-1}\equiv b (\%k-1),sum_r-b\equiv sum_{l-1}(\%k-1)\)

  Code

#include
    
     typedef long long LL;const LL maxn=1e6+9;inline LL Read(){    LL x(0),f(1); char c=getchar();    while(c<'0' || c>'9'){        if(c=='-') f=-1; c=getchar();    }    while(c>='0' && c<='9'){        x=(x<<3)+(x<<1)+c-'0'; c=getchar();    }return x*f;}LL k,b,n,ret,num,ze;LL a[maxn],sum[maxn];std::map
     
       cnt;int main(){    k=Read(); b=Read(); n=Read();    for(LL i=1;i<=n;++i) a[i]=Read();    for(LL i=1;i<=n;++i){        sum[i]=(sum[i-1]+a[i])%(k-1);        if(!a[i]){            ++num;            ze+=num;        }else            num=0;    }    if(!b){        printf("%lld\n",ze);        return 0;    }    cnt[0]++;    for(LL i=1;i<=n;++i){        LL val((sum[i]-b+k-1)%(k-1));        ret+=cnt[val];        ++cnt[sum[i]];    }    if(b==k-1) ret-=ze;    printf("%lld\n",ret);    return 0;}