Codeforces 213B Numbers

問題

n桁の正整数であって、
0, 1, 2... ,9の数字がそれぞれa[0], a[1], ..., a[9]回以上現れるようなものはいくつあるか、求めよ。
leading zeroは許されない。

制約条件

n≦100

方針

桁数を決めうちして、それぞれ全部DPで求める。
DPは、0から順に場所を決めていく。
dp[i][j]を、数字をiまで決めて、残っている場所がj個ある状態での場合の数。
iがa[i]以上現れるという条件は遷移で実現できる。

ソースコード

const int mod = (int)1e9 + 7;
int n, a[10], dp[11][110], C[110][110];

int solve(int n){
	int cnt = 0;
	rep(i, 10) cnt += a[i];
	if(cnt > n) return 0;
	if(cnt == n && a[0] == n) return 0;
	if(n == 1) return cnt == 0 ? 9 : 1;
	
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	rep(i, 10) rep(j, n + 1) if(dp[i][j]){
		for(int k = a[i]; j + k <= n; k++){
			ll way = i == 0 ? C[n-1][k] : C[n-j][k];
			dp[i+1][j+k] = dp[i+1][j+k] + dp[i][j] * way % mod;
			dp[i+1][j+k] %= mod;
		}
	}
	return dp[10][n];
}

int main(){
	cin >> n;
	rep(i, 10) cin >> a[i];
	rep(i, 110) rep(j, i+1) C[i][j] = j == 0 || j == i ? 1 : (C[i-1][j-1] + C[i-1][j]) % mod;
	
	ll ans = 0;
	for(int i = 1; i <= n; i++) ans += solve(i);
	cout << ans % mod << endl;
	return 0;
}