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; } };