Nowcoder84D

很有趣的进制转换题！

如果x满足题意，那么x+k-1一定能符合要求！

因为k-1用k进制表示就是1,-1,1+(-1)=0所以数位之和不变！

用map维护一下前缀和。就好了。

#include <iostream>

#include <map>

using namespace std;

typedef long long LL;

const int N=100002;

LL k,b,n;

LL a[N],s[N],s2[N];

map<LL,LL> mp,mp2;

int main() {

    scanf("%lld%lld%lld",&k,&b,&n);

    for(int i=1;i<=n;i++) {

        scanf("%lld",&a[i]);

        s2[i]=s2[i-1]+a[i]; mp2[s2[i]]++;

        a[i]%=(k-1); s[i]=s[i-1]+a[i]; s[i]%=(k-1);

        mp[s[i]] ++;

    }

    mp[0]++; mp2[0]++;

    LL ret=0,zero=0;

    for(int i=0;i<=n;i++) {

        mp2[s2[i]] --;

        zero += mp2[s2[i]];

    }

    for(int i=0;i<=n;i++){

        mp[s[i]] --;

        ret += mp[(s[i]+b)%(k-1)];

    }    

    if (b==0) {

        ret = zero;

    }

    if (b==k-1) {

        ret -= zero;

    }

    cout<<ret<<endl;

}

巴特西

Nowcoder84D

Nowcoder84D

最新文章

热门文章