SRM720 Lv1 : SumProduct
作成日：2017.08.31
最終更新日：2017.08.31
問題概要
数字$i(0 \leq i \leq 9)$が$amount_i$個ある。
これらの数字を用いて10進法で$blank1$桁の数$A$と$blank2$桁の数$B$を作る。
$A,B$ともに先頭に$0$が続いても構わない。
この時異なる$A,B$の組それぞれにおいて積を計算し、その総和を$mod \: 10^9 + 7$で求めよ。
制約
$0 \leq amount_i \leq 100$
$1 \leq blank1,blank2 \leq 100$
$blank1 + blank2 \leq \sum{amount_i}$
考え方
先頭に$0$が続いても良いことから、$A$の各桁及び$B$の各桁は$10$の累乗倍を無視すれば等価である。
また$A,B$のいずれかの1つの桁だけを固定して考えるのは、積を取る処理が難しい。
よって$A,B$それぞれ1桁の数を選んで決めた時に残りの$(blank1 + blank2 - 2)$桁の並べ方が何通りあるかを求めることにする。
残りの桁の並べ方は、それを構成する数がそれぞれ何個あるかが分かれば重複順列なので求めることができる。
重複順列は${n!}/\prod{a!}$で求められるから、数ごとに何個取るかを順に決めていきその個数の階乗で割ったものの総和を取るDPで目的のものが得られる。
この方法の計算量は$O((桁数)^3(blank1+blank2))$なので十分高速である。
ソースコード
マクロ等はこちら
const LL mod = 1e9 + 7;
const int MC = 222;
LL pw(LL a , LL b){
LL c = 1;
LL d = a;
for(int i = b ; i > 0 ; i >>= 1){
if(i&1) (c *= d) %= mod;
d = d * d % mod;
}
return c;
}
class SumProduct {
LL p[MC]; //10^i
LL fc[MC]; //i!
LL inv[MC]; //(i!)^-1
LL dp[11][MC];
public:
int findSum(vector<int> amount, int blank1, int blank2) {
p[0] = 1;
repp(i,1,MC) p[i] = p[i-1] * 10 % mod;
fc[0] = 1;
repp(i,1,MC) fc[i] = fc[i-1] * i % mod;
inv[MC-1] = pw(fc[MC-1],mod-2);
repm(i,MC-1,0) inv[i-1] = inv[i] * i % mod;
int n = blank1+blank2-2;
LL f = 0;
repp(i,1,10){
if(amount[i] == 0) continue;
--amount[i];
repp(j,1,10){
if(amount[j] == 0) continue;
--amount[j];
fill(dp[0],dp[0]+n+1,0);
dp[0][n] = fc[n];
repp(x,0,10){
fill(dp[x+1],dp[x+1]+n+1,0);
repm(y,n,-1){
repm(z,min(y,amount[x]),-1){
(dp[x+1][y-z] += dp[x][y] * inv[z]) %= mod;
}
}
}
++amount[j];
(f += i * j * dp[10][0]) %= mod;
}
++amount[i];
}
LL ans = 0;
repp(i,0,blank1){
repp(j,0,blank2){
(ans += f * p[i+j]) %= mod;
}
}
return (int)ans;
}
};解法まとめ
$A,B$それぞれ1桁の数を選んで決めた時の残りの桁の並べ方$f$をDPで求める。(27-49行)
桁を選ぶ位置を定めて足し合わせる。(50-55行)
SRM720の他の問題 Lv2 Lv3