Codeforces #181 Div2 C "Beautiful Numbers"
問題
http://codeforces.com/contest/300/problem/C
訳
ヴィタリーは奇妙な男である。
彼はa, bという2つの数字が好きである。
ヴィタリーは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; }