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; }