TopCoder SRM 720 Div1 Easy SumProduct

競プロ TopCoder

問題文

リンクがまだない

問題概要

あなたは 0 から 9 までの数字をそれぞれ a[i] 個使えるとします．
これらの数字から，A 桁の数字 X と B 桁の数字 Y の2つの数字を作るとします．
このとき，考えられる (X, Y) について，X * Y の総和を求めなさい．
ただし，0-leadingな数字も許可するとし，また (a, b) と (b, a) (a != b) は区別して扱います．

例．
1を2個，2を1個，3が1個使えて，A = 2, B = 2の時，考えられるすべてのペアは
(11, 23), (11, 32), (12, 13), (12, 31), (13, 12), (13, 21), (21, 13), (21, 31), (31, 12), (31, 21), (32, 11) の12個で，総和は4114です．

・制約
0 <= a[i] <= 100
1 <= A <= 100
1 <= B <= 100
A + B <= a[0] + a[1] + ... + a[10]

解法

まず，0-leadingな数字が許される（例えば 0001 は 1 として扱う）ので，ある1つの桁に注目すると，その桁が x であるような組み合わせの数は，その桁以外でも全く同じになることがわかります．
（例えば，X の10の位が x である場合の数と，X の1000の位が x である場合の数は等しい．）
これから，以下のような解法が考えられます．

X の i 桁目が x，Y の j 桁目が y であるような組み合わせを C とおくと，ans += x * 10^i * y * 10^j * C をすべての i, x, j, y について行う．

各桁だけ抽出してやっていくということです．
先程も行ったとおり，何桁目だろうが同じことなので，X で x を1桁目に使い，Y で y を1桁目に使う場合の数を求めるだけで十分です．
これは
dp[i + 1][j] := 数字 i まで見た時，すでに j 桁使っている場合の数
として求めることができます．数字は結局 A + B 桁選ぶことになり，x と y は1つ使うのが固定なので，dp[10][A + B - 2] 通りが求める場合の数になります．a[x] と a[y] から最初に1を引いておくことに注意は必要です．
このDPの遷移は，今できている数列に，今見ている数字をいくつ挿入するか決め，そのあと配置をを定める，ということを考えるとかけます．
もしすでに j 桁できていて，k 個数字を挿入するなら，残りの A + B - 2 - j 箇所から k 箇所選んで配置するということです．

あとは，tmp += dp[10][A + B - 2] * x * y としていくと，最終的に tmp はある桁に注目したときの，その桁のみの掛け算の総和となります（10 のべき乗部分を含めていません）

最後は，i 桁と j 桁を全部試して足せばいいです．
これは tmp * 10^i + tmp * 10^j を，0 <= i < A, 0 <= j < B についてループを回すだけです．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
constexpr ll M = 1e9 + 7;

ll modpow(ll x, ll n) {
    ll res = 1;
    while(n > 0) {
        if(n & 1) {
            res = (res * x) % M;
        }
        x = (x * x) % M;
        n >>= 1;
    }
    return res;
}

class SumProduct {
public:
    int findSum(vector<int> amount, int blank1, int blank2) {
        vector<vector<ll>> comb(201, vector<ll>(201));
        for(int i = 0; i < 201; ++i) {
            for(int j = 0; j <= i; ++j) {
                if(j == i || j == 0) {
                    comb[i][j] = 1;
                } else {
                    comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]) % M;
                }
            }
        }

        ll t = 0;
        for(int n = 0; n <= 9; ++n) {
            if(amount[n] - 1 < 0) {
                continue;
            }
            amount[n]--;
            for(int m = 0; m <= 9; ++m) {
                if(amount[m] - 1 < 0) {
                    continue;
                }
                amount[m]--;
                vector<vector<ll>> dp(11, vector<ll>(201));
                dp[0][0] = 1;
                for(int i = 0; i < 10; ++i) {
                    for(int j = 0; j <= blank1 + blank2 - 2; ++j) {
                        for(int k = 0; k <= amount[i] && j + k <= blank1 + blank2 - 2; ++k) {
                            (dp[i + 1][j + k] += comb[blank1 + blank2 - 2 - j][k] * dp[i][j]) %= M;
                        }
                    }
                }
                t = (t + n * m * dp[10][blank1 + blank2 - 2]) % M;
                amount[m]++;
            }
            amount[n]++;
        }
        ll res = 0;
        for(int i = 0; i < blank1; ++i) {
            for(int j = 0; j < blank2; ++j) {
                res = (res + (t * modpow(10, i) % M) * modpow(10, j)) % M;
            }
        }
        return res;
    }
};

感想

本番で通せませんでした．DP部分ができない～となっていましたが，本番終了後に既知のDPであることに気が付きました．
過去の自分をぶんなぐってやりたい．