Div.1 B ＆ Div.2 D : Numbers

問題概要

各数字を特定回数以上使って構成できる、n 桁以下の数はいくつあるか。mod で示せ。

考え方

まず "n 桁以下の数" という条件が面倒なので、一旦 "k 桁の数" と考えなおしてみる。結局はこの k を でループして計算すればいいだけの話なので。
とりあえず 0 は最上位に入らないので パターン( パターンの組み合わせがある。なのでこの関係を DP で計算することになる。今回のプログラムでは [数字 d][既に埋めている桁数 k][数字 d を使っている個数 j] という風に組んでいる。

コード

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
typedef long long int64;
const int64 MOD =1000000007ll;
int comb[101][101];
int64 Comb(int n, int k) {
  if (comb[n][k]) return comb[n][k];
  if (n == k || k == 0) return comb[n][k] = 1;
  return comb[n][k] = (Comb(n - 1, k) + Comb(n - 1, k - 1)) % MOD;
}
int64 dp[10][101][101];
int Solve(const int n, const int *a) {
  int64 m = 0;
  for (int i = 0; i < 10; ++i) m = m + a[i];

  int64 sum = 0;
  for (; m <= n; ++m) {
    memset(dp, 0, sizeof(dp));
    // 0 だけ特別処理
    for (int i = a[0]; i <= m - 1; ++i) dp[0][i][i] = Comb(m - 1, i);
    for (int d = 1; d < 10; ++d) for (int k = 0; k <= m; ++k) for (int j = 0; j <= k; ++j) for (int i = a[d]; i <= m - k; ++i) {
            int64 add = dp[d - 1][k][j] * Comb(m - k, i) % MOD;
            dp[d][k + i][i] = (dp[d][k + i][i] + add) % MOD;
          }
    for (int i = a[9]; i <= m; ++i) sum = (sum + dp[9][m][i]) % MOD;
  }
  return sum;
}
int main(void) {
  int a[10], n;
  cin >> n;
  for (int i = 0; i < 10; ++i) cin >> a[i];
  cout << Solve(n, a) << "\n";
  return 0;
}