同じ方針でやっている人があまりいなさそうなので一応書きます。
問題概要
日本語なので原文を参照してください → Card | Aizu Online Judge
解説
整数を組み合わせて最終的に という数を作ったとします。与えられるそれぞれの整数について、その整数の 1 の位が
の何の位として使用されている通り数が何通りあるかがわかれば、元の問題が解けます。ここまでは公式解説の方針と同じです。
さて、整数 について組み合わせを求めるとき、それ以外の整数について並べ方を考慮しなければなりません。特に、
より低い位に並べる整数について、その桁数が合計で何桁になるかは答えを求める際に重要な情報です。また、低い位で整数をいくつ使ったかがわからないと、
より高い位に整数を最大でいくつ使えるかがわかりません。よって、
より低い位に、整数を「何個」並べているか
の情報が必要になります。
これを処理するために DP を考えます。dp[i][j][k] := i 番目の整数まで見て、そのうち j 個を使用し、使用した整数の桁数の合計が k であるような状態の通り数 とします。
しかしここで問題となるのが、 について通り数を考えるときは DP 内で
番目を選んではいけない ことです。
番目を必ず選ばないとしたときの通り数を求めるために、ここで戻す DP のテクニックを使います。
先ほど定義した DP は、実際に書くと以下のような遷移になります。(説明のため、「何番目の要素まで処理したか」に相当する 1 次元目を省略せずに書いています)
int sum = 0; for(int i=0; i<N; i++) { sum += digit[i]; // i 番目の整数の桁数 for(int j=0; j<=i; j++) { for(int k=0; k<=sum; k++) { dp[i+1][j][k] += dp[i][j][k]; // その整数を使わない if(k + digit[i] <= sum) dp[i+1][j+1][k+digit[i]] += dp[i][j][k] * (j + 1); // その整数を使う } } }
この遷移をひもといていくと、dp[i+1][j][k] = dp[i][j][k] + dp[i][j-1][k-digit[i]] * j が成立します。
これを移項すると dp[i][j][k] = dp[i+1][j][k] - dp[i][j-1][k-digit[i]] * j となります。この式は、i+1 番目の状態から i 番目の状態に戻していることを表します。今回は整数を使用する順番が通り数に依存しないので、i を N 番目の整数とみなすと dp2[i][j][k] = dp[N][j][k] - dp2[i][j-1][k-digit[i]] * j とできます。ここで、dp2[i][j][k] := i 以外の全ての整数を考慮し、その中で j 個使って桁数が k になるような状態の通り数 です。
このような情報が得られていれば元の問題を解くことができます。0 の処理が面倒ですが場合分けすればできます。
ソースコード
ll dp[201][805], tmp[201][805]; ll pw[805], tab[201], tab_zero[201]; signed main() { int N; cin >> N; pw[0] = 1; for(int i=1; i<805; i++) { pw[i] = (pw[i-1] * 10) % MOD; } // tab[i] = iP0 + iP1 + ... iPi for(int i=0; i<=N; i++) { tab[i] = 1; ll P = 1; for(int k=1; k<=i; k++) { (P *= i - k + 1) %= MOD; (tab[i] += P) %= MOD; (tab_zero[i] += P * k % MOD) %= MOD; } } bool exist_zero = false; vector<int> A, digits; for(int i=0; i<N; i++) { int val; cin >> val; if(val == 0) { exist_zero = true; continue; } else A.push_back(val); int d = 0; while(val) d++, val /= 10; digits.push_back(d); } int M = A.size(), sum = 0; dp[0][0] = 1; for(int i=0; i<M; i++) { for(int j=i; j>=0; j--) { for(int k=sum; k>=0; k--) { (dp[j+1][k+digits[i]] += dp[j][k] * (j + 1)) %= MOD; } } sum += digits[i]; } // i 番目を使わない場合 ll ans = 0; for(int i=0; i<M; i++) { fill(tmp[0], tmp[M+1], 0); for(int j=0; j<M; j++) { for(int k=0; k<=sum; k++) { tmp[j][k] = dp[j][k]; if(j - 1 >= 0 and k - digits[i] >= 0) { (tmp[j][k] += MOD - (tmp[j-1][k - digits[i]] * j % MOD)) %= MOD; } // j 個を使って合計 k 桁 (これを i 番目の下に置くイメージ) // 残っているのは M-j-1 個 { // 0 を使わない場合 ll comb = tab[M-j-1] * tmp[j][k] % MOD; ll val = A[i] * pw[k] % MOD; ll add = val * comb % MOD; (ans += add) %= MOD; } if(exist_zero) { // 0 を使う場合 (i 番目の下に置く) { ll comb = tab[M-j-1] * tmp[j][k] % MOD * (j+1) % MOD; ll val = A[i] * pw[k + 1] % MOD; ll add = val * comb % MOD; (ans += add) %= MOD; } // 0 を使う場合 (i 番目の上に置く) { ll comb = tab_zero[M-j-1] * tmp[j][k] % MOD; ll val = A[i] * pw[k] % MOD; ll add = val * comb % MOD; (ans += add) %= MOD; } } } } } cout << ans << endl; return 0; }
