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から考えて,そこから少しずつオーダー落としていくと楽だった.
でもまあ結構めんどくさかった.