Topcoder SRM 720 Div1 Easy - SumProduct

問題概要

0~9の各数字について、それぞれを何回まで使ってよいかを示した配列amountが与えられる。amountの制限を守って桁数がblank1の非負整数A, blank2の非負整数Bをつくるとき、ありえるA, Bのすべての組合せにおけるA*Bの総和を求めよ。

max(amount) <= 100

blank1, blank2 <= 100

解法

Aのi桁目に使う数字aとBのj桁目に使う数字bを固定する。このケースにおけるA*Bの総和は

(10i * a) * (10j * b) * (他の数字の並べ方)

となる。他の数字の並べ方とはつまり固定した2桁以外にどう数字を配置するかということで、これはDPで求めることができる。

dp(i, j) = 0~iまでの数字を使ったときの、j桁の数の作り方の総数

遷移は既に構成してる数字の並びに対して数iを差し込んでいくというイメージで考えるとコンビネーションを使ってできる (ei1333さんのブログがわかりやすかったです)。

感想

easyとは何か?

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;

const ll MOD = 1000000007;
const ll MAX = 201;
ll comb[MAX][MAX];
ll dp[10][MAX];

ll powmod(ll a, ll x, ll m) {
    ll ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

class SumProduct {
public:
    int findSum(vector<int> amount, int blank1, int blank2) {
        ll ans = 0;

        comb[0][0] = 1;
        comb[1][0] = 1;
        comb[1][1] = 1;
        REP2(i, 2, MAX) REP(j, MAX) {
            comb[i][j] = (j == 0 || j == i) ? 1 : (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
        
        
        REP(a, 10) REP(b, 10) {
            amount[a] -= 1;
            amount[b] -= 1;
            if (amount[a] < 0 || amount[b] < 0) {
                amount[a] += 1;
                amount[b] += 1;
                continue;
            }

            memset(dp, 0, sizeof(dp));
            REP(j, MAX) dp[0][j] = j <= amount[0] ? 1 : 0;
            REP2(i, 1, 10) REP(j, MAX) REP(k, amount[i] + 1) {
                if (j - k < 0) continue;
                (dp[i][j] += dp[i-1][j - k] * comb[j][k] % MOD) %= MOD;
            }


            REP(i, blank1) REP(j, blank2) {
                ll tmp = 1;
                tmp = tmp * a * powmod(10, i, MOD) % MOD;
                tmp = tmp * b * powmod(10, j, MOD) % MOD;
                tmp = tmp * dp[9][blank1 + blank2 - 2] % MOD;
                ans = (ans + tmp) % MOD;
            }
            
            amount[a] += 1;
            amount[b] += 1;
        }

        return (int)ans;
    }

};