Live archive 5063 Just Sum It

Just Sum It
http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=388&page=show_problem&problem=3064

問題概要

１〜９までの数字について、それぞれ使える回数が与えられる。
その数字を使える回数以下で並べたときの作ることができる数のすべての合計を求めよ。

解法

DP
１ まず、どの数字に注目するか決める。
２ 桁数を決める。
３ 注目した数字以外で決めた桁数の数字の作れる種類数を求める。つまり、重複順列の一部の種類数。
４ すべての桁に注目した数字を挿入したとき場合を考え合計を求める。
その重複順列の求め方をDPで求める。
dp[i][j] iまでの数字を用いて、j桁の数字を作れる種類数。
これを状態にし、
for k 0-> i番目の数字の使える数
dp[i][j] += dp[i-1][j-k] * jCk
となる。
つまり、i番目の数字を使う場所を選ぶのを組み合わせで求める。

ソース

#include <iostream>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;

const int C = 100;
typedef unsigned long long lli;

lli comb[C][C];
const lli MOD = 1000000007;
void makeComb(){
  rep(i, C){
    rep(j, C){
      comb[i][j] = 0;
    }
  }
  comb[0][0] = 1;
  REP(i, 1, C){
    comb[i][0] = 1;
    REP(j, 1, i+1){
      comb[i][j] = comb[i-1][j] + comb[i-1][j-1];
      comb[i][j] %= MOD;
    }
  }
}



int main(){
  makeComb();
  int T;
  cin >> T;
  rep(tc, T){
    int t[10];
    lli ten[101];
    ten[0] = 1;
    REP(i, 1, 101){
      ten[i] = 10 * ten[i-1];
      ten[i] %= MOD;
    }
    REP(i, 1, 10)cin >> t[i]; 
    lli ans = 0;
    REP(now, 1, 10){
      t[now]--;
      if(t[now] < 0){
        t[now]++;
        continue;
      }
      lli dp[10][100];
      rep(i, 10)rep(j, 100)dp[i][j] = 0;
      dp[0][0] = 1;
      REP(i, 1, 10){
        rep(j, 100){
          rep(k, t[i]+1){
            if(j-k < 0)continue;
            dp[i][j] += (dp[i-1][j-k] * comb[j][k])%MOD;
            dp[i][j] %= MOD;
          }
        }
      }
      rep(i, 100){
        rep(j, i+1){
          ans += now * ((dp[9][i] * ten[j])%MOD);
          ans %= MOD;
        }
      }
      t[now]++;
    }
    cout << ans << endl;
  }
}