Codeforces #181 Div2. C. Beautiful Numbers

CF181はDiv2 Onlyなので復習のみ。
http://codeforces.com/contest/300/problem/C

問題

１桁の数値a,bに対し、その２種類の数字だけで作られた10進数の値はgoodである。
さらに、goodな数値の各桁の和がさらにgoodなら、その値はexcellentである。
a,bおよび桁長Nが与えられたとき、N桁のexcellentな数値の種類を返せ。

解法

aをi個、bを(N-i)個用いたとき、a*i+b*(N-i)がgoodならその数値はexcellentになる。
よってそのようなiに対し[tex:{}_N C_i}を累積すればよい。

int A,B,N;
ll mo=1000000007;

ll combi(ll N_, ll C_) {
	int i;
	const int num=1000005;
	static ll rev[num+1],revt[num+1];
	
	if(rev[1]==0) {
		rev[1]=1; for(i=2;i<=num;i++) rev[i]=rev[mo%i]*(mo-mo/i)%mo;
		revt[0]=1; for(i=1;i<=num;i++) revt[i]=revt[i-1]*rev[i]%mo;
	}
	ll ret=revt[C_];
	FOR(i,C_) ret = (ret * ((N_-i)%mo))%mo;
	return ret;
}

int good(int num) {
	int t=0;
	while(num) {
		if(num%10!=A && num%10!=B) return 0;
		num/=10;
	}
	return 1;
}

void solve() {
	int f,r,i,j,k,l, x,y,ma,num,nt;
	ll tot = 0;
	
	cin>>A>>B>>N;
	FOR(i,N+1) if(good(A*i+B*(N-i))) tot = (tot + combi(N,i)) % mo;
	cout << tot << endl;
	
	return;
}

まとめ

ここら辺はまだそれほど難しくない問題。