天下一プログラマーコンテスト2014 決勝 : A - 塙さん

当然オンサイト出場はしていないので、オンライン参加。
ABはさっさと解けたが、その後難しい問題が部分点しか取れないといういつも通りの結果。
Aが会場とオンライン両方合わせてFirst Acceptだったのはよかった。
http://tenka1-2014-final-open.contest.atcoder.jp/tasks/tenka1_2014_final_a

問題

整数h,n,wが与えられる。
w桁のh進数のうち、先頭が0ではなく、各数値がn回以下しか登場しないようなものの数を答えよ。

解法

h種類の数字をn回以下使って、計w桁作る作り方をDPかメモ化再帰で作ればよい。
「先頭が0でない」の条件は、最後に全体の答えを(h-1)/h倍するだけ。

以下では「残りW桁をH種類の数字で埋める」というメモ化再帰を行っている。
各数字はi=0～min(n,W)回利用でき、その文字が入る場所は通りある。

int H,N,W;
ll mo=1000000007;
ll memo[70][3000];


ll rev(ll a) {
	ll r=1, n=mo-2;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll comb(int P_,int Q_) {
	static const int N_=2520;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j])%mo;
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}

ll dodo(int h,int w) {
	if(h<=0) return w==0;
	if(memo[h][w]>=0) return memo[h][w];
	int i;
	ll& ret=memo[h][w];
	ret=0;
	FOR(i,min(N,w)+1) ret+=comb(w,i)*dodo(h-1,w-i)%mo;
	return ret%=mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	cin>>H>>N>>W;
	
	ll ret=dodo(H,W);
	cout << ret*(H-1)%mo*rev(H)%mo << endl;
}

まとめ

これはすんなり。