AOJ 2436 Card
解法
カードの数字同士を足すわけではなくそのまま並べるので,桁に注目したいなーという気持ちになります.
しかも $a[i]$ は高々4桁なので嬉しいです.
こういう問題は,すべての数字をまとめてやるのは大変な気がするので,ある $a[i]$に着目してやってみましょう.
つまり,$a[i]$ を $j$ 桁目に並べるような並べ方が何通りあるかさえわかれば,それを $C$ 通りだとすると,$a[i] \times 10^j \times C$ を答えに加えるということをすればよいことになります.
さて,例えば $X$ が $j$ 桁めにあるようなものをカウントしましょう.
それは以下のような感じになります.
.......($X$ の前に数字が並ぶ) $X$ ($X$ のあとに $j$ 桁並ぶ)........
当たり前ですが,前と後ろで独立に考えられます.まず後ろを考えましょう.
後ろは以下のようなdpで求めることが出来ます.
$dp[i][j] := X$ 以外の $i$ 枚のカードを並べて $j$ 桁にする場合の数(ゼロリーディングを含める)
遷移の式は簡単ですね.
しかしこのままでは,注目する数 $X$,今追加して並べようとする数 $a[j]$,すでに並べている枚数 $k$,すでに出来ている桁数 $l$,の4つでループが回るので間に合いません.
しかしよく考えると,同じ桁数である $a[i]$ と $a[j]$ について dp の値は全く同じであることがわかります.なので,この計算はループの外に逃がすことが出来ます.以降,dp のキーに桁数を追加して説明することとします.
さて,dp テーブルが求まったら,前に並ぶ数字も考えて最終的な答えを求めにいきます.
今注目している数字が $a[i]$ で,$a[i]$ が $d[i]$ 桁であり,後ろで $j$ 枚のカードを使っていて,それが $k$ 桁であり,前に $l$ 枚のカードを並べるとき,$\displaystyle \sum_{l = 0}^{n - 1 - j}(_{n-1-j}C_{l} \times l! \times a[i] \times 10^j \times dp[d[i]][j][k])$
残念ながら,これも4重ループになっていますが,先と同様,同じ桁である $a[i]$ をまとめて処理してやるとオーダーが落とせます.$sum[x] := x$桁である$a[i]$の総和とすれば,$a[i]$ の部分を $sum[i]$ にしてやればOKです.
最後にゼロリーディングの処理ですが,これは最初に0である$a[i]$を1つだけ取り除いたカード列について同じ計算をして,最後に0を先頭にくっつけたものを引く,という処理で実現できます.先頭の0をどの0にするか,を書け忘れないように.
計算量は O(4 * N^3) になります.
ソースコード
#include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; using ll = long long; constexpr ll M = 1e9 + 7; ll ten_pow[1024]; ll fact[256]; ll comb[256][256]; void init() { ten_pow[0] = 1; for(int i = 1; i < 1024; ++i) { ten_pow[i] = (ten_pow[i - 1] * 10) % M; } fact[0] = 1; for(int i = 1; i < 256; ++i) { fact[i] = (fact[i - 1] * i) % M; } for(int i = 0; i < 256; ++i) { for(int j = 0; j < 256; ++j) { if(i == j || j == 0) { comb[i][j] = 1; } else { comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % M; } } } } ll solve(vector<int> const& a, vector<int> const& d) { int const n = a.size(); vector<vector<vector<ll>>> dp(5, vector<vector<ll>>(n, vector<ll>(n * 4 + 1))); ll res = 0; vector<ll> sum(5); for(int i = 0; i < n; ++i) { sum[d[i]] = (sum[d[i]] + a[i]) % M; } for(int i = 0; i < n; ++i) { if(dp[d[i]][0][0] == 0) { dp[d[i]][0][0] = 1; for(int j = 0; j < n; ++j) { if(i == j) { continue; } for(int k = n - 1; k >= 0; --k) { for(int l = 0; l < n * 4 + 1; ++l) { if(dp[d[i]][k][l] == 0) { continue; } dp[d[i]][k + 1][l + d[j]] = (dp[d[i]][k + 1][l + d[j]] + dp[d[i]][k][l] * (k + 1)) % M; } } } } } for(int i = 0; i < 5; ++i) { for(int j = 0; j < n; ++j) { for(int k = 0; k < 4 * n + 1; ++k) { if(dp[i][j][k] == 0) { continue; } for(int l = 0; l <= n - 1 - j; ++l) { ll t = (sum[i] * dp[i][j][k]) % M; t = (t * ten_pow[k]) % M; t = (t * comb[n - 1 - j][l]) % M; t = (t * fact[l]) % M; res = (res + t) % M; } } } } return res; } int main() { init(); int n; cin >> n; int zero_cnt = 0; vector<int> a(n); vector<int> d(n); for(int i = 0; i < n; ++i) { cin >> a[i]; d[i] = to_string(a[i]).size(); zero_cnt += (a[i] == 0); } ll res = solve(a, d); if(zero_cnt != 0) { int idx = find(begin(a), end(a), 0) - begin(a); a.erase(a.begin() + idx); d.erase(d.begin() + idx); ll leading_zero = (zero_cnt * solve(a, d)) % M; res = (res - leading_zero + M) % M; } cout << res << endl; }
感想
自明なDPから考えて,そこから少しずつオーダー落としていくと楽だった.
でもまあ結構めんどくさかった.