SRM482 Div2 Hard(900) BaseConfusion

TopCoder

BaseConfusion

Nまでの合計をs(N,B)とすると、答えはs(N,B)-s(M-1,B)。
s(N,B)は各桁に各数字がいくつ含まれているかを考える。例えばs(12,3)=0+1+2+10+11+12+20+21+22+100+101+102+110について、10の位には1が4個含まれていて、B+1を基数としたとき1*4*(B+1)になる。

long long s( int N, int B )
{
    long long r = 0;

    for ( long long b1=1, b2=1; b1<=N; b1*=B, b2*=B+1 )
        for ( int d=0; d<B; d++ )
            r += ( (N/b1+B-d-1)/B*b1 + (N/b1%B==d?N%b1+1:0) ) * d * b2;

    return r;
}

class BaseConfusion{public:
long long sum( int M, int N, int B )
{
    return s(N,B) - s(M-1,B);
}};