Codeforces #181 Div2 C "Beautiful Numbers"

問題

http://codeforces.com/contest/300/problem/C

訳

ヴィタリーは奇妙な男である。
彼はa, bという２つの数字が好きである。
ヴィタリーは10進数表記でa, bのみで構成されている正の整数を、goodだとしている。
ヴィタリーはgoodな数において、その数字を全て足した数がgoodであれば、
excellentだとしている。

例えば、ヴィタリーの好きな数字が1と3だとしよう。
すると、12はgoodではなく、13や311はgoodである。
また、111はexcelentであるが、11はそうではない。

ヴィタリーは長さがちょうどnの、excellentな数字が
いったいどれほどあるのか知りたいと思っている。

長さnのexcellentな数字の存在する数を出力せよ。

数の長さとは、その数を10進数表記したときの、先頭の0を覗いたときの桁数である。

制約

1 <= a < b <= 9
1 <= n <= 10^6

考えた事

excellentな数の数字の合計値の範囲は
a * n から b * nに収まり、
これはa = 1 b = 9 n = 10^6の時が最も広くなり、
高々800万になる。

この数値を、
goodなのか？
aとbをn個使ってその合計値になるか？
を一つ一つ調べていけばよい。

excellentとしていけるようであれば、
a（またはb）の使う数を出し、
nCa（またはnCb)を計算して足していく。

ソースコード

const int MOD = 1000000007;
int A, B, N;
long long C[1000050]; // nCi

// a^b % MOD
long long mod_pow( long long a, int b ){
    long long r = 1;
    while( b > 0 ){
        if( b & 1 ) r = r * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return r;
}

// aの逆元
long long mod_inv( long long a ){
    return mod_pow( a, MOD - 2 );
}

// Cを初期化
void initC(){
    C[0] = 1;
    for( int i = 1; i <= N; i++ ){
        C[i] = C[i-1] * ( N - i + 1 ) % MOD * mod_inv( i ) % MOD;
    }
}

// numを文字列にする
void getString( int num, char* buf ){
    int i = 0;
    for( ; num > 0; i++ ){
        buf[i] = (num % 10) + '0';
        num /= 10;
    }
    buf[i] = '\0';
}

int main() {

    cin >> A >> B >> N;
    initC();

    int minNum = A * N;
    int maxNum = B * N;

    long long res = 0;
    // 合計値を一つ一つ調べていく
    for( int num = minNum; num <= maxNum; num++ ){
        // 文字列にする
        char buf[256];
        getString( num, buf );
        
        // AとBのみで構成されているか調べる
        bool ok = true;
        for( int i = 0; i < strlen( buf ); i++ ){
            int n = buf[i] - '0';
            if( n != A && n != B ){
                ok = false;
                break;
            }
        }

        // AとB以外が入っていた
        if( !ok ) continue;
        // AとBをN個使ってその合計値は作れなかった
        if( (num - minNum) % (B - A) ) continue;

        // Bを何個使えばいいのか？
        int b = (num - minNum) / (B - A);
        // nCbを足す
        res = (res + C[b]) % MOD;
    }
    
    cout << res << endl;
}