今回は、 yukicoder の問題紹介・解説を行っていきたいと思います！
１発目に紹介する問題はこちら！
問題 ： No.1629 Sorting Integers (SUM of M)
レベル ： ★★
実行時間制限 ： 2000 ms
問題文へのリンク↓↓
問題文
$1$ 桁の正整数が $N$ 個あります． このうち $i$ は $c_{i}$ 個です $(1 \leq i \leq 9)$．
これら $N$ 個の整数を並べ替え， それを $N$ 桁の $10$ 進法の整数 $M$ とみなしたとき， $M$ として考えられるものの 総和 を求めてください．
ただし， 答えは非常に大きくなる可能性があるので $10^9 + 7$ で割った余りを出力してください．
入力
- $1 \leq N \leq 2 \times 10^5$
- $c_{i} \geq 0$
- $\sum_{i=1}^{9}c_{i} = N$
- 入力は全て整数
入力例
入力
3
1 1 1 0 0 0 0 0 0
出力
1332
$1,2,3$ が $1$ ずつあり、 $M$ として考えられるものは、 $123,132,213,231,312,321$ があるので、$123 + 132 + 213 + 231 + 312 + 321 = 1332$ となります。
解説
ここからは解説をしていきます。
自力で解いて見たい方はここでストップしてください！
組み合わせの総数
まずは愚直にこの問題を解くことを考えてみます。考えられる総数は以下のように求められます。
\frac{N!}{\sum_{i=1}^{9}c_{i}!}
これを１つ１つ足していっては、とても間に合いません。
この式が理解出来ない方は、以下の記事を参考にして見てください。
ググってわかりやすそうだったので載せておきます。
ここで計算量を減らす考え方として有効なのが、 各桁ごとに考える ということです。
具体例を考える
例えば、以下のような入力例の場合について考えて見ましょう。
8
0 0 2 3 2 1 0 0 0
この場合だと $8$ 桁の数字を作ることになります。例えば、 $53644534$ が作れますね。
考えられる組み合わせは以下の通り数あります。
\frac{8!}{2!3!2!1!} = \frac{40320}{24} = 1680
では $1680$ 通りのうち、 $100$ の位が $4$ になる場合の数が何個あるか計算してみましょう。
答えは以下の式で求められます。
\frac{7!}{2!(3-1)!2!1!} = \frac{5040}{8} = 630
$100$ の位以外の全ての組み合わせを求めれば良いので、桁数は $1$ 桁減り 7 になり、
分母も $4$ が $1$ つ減ったので、$(3-1)!$ となります。
つまり、桁ごとに独立で考えると、 $100$ の位が $4$ になる場合は $630$ 通りあるので、
この総数は、 $\displaystyle 4 \times 100 \times 630 = 252000$ であるということがわかります！
一般化
では、これを一般化することを考えてみましょう。
$10^k$ が $i$ の時の合計はいくつになるかというと以下のような式で求められます。 $(0 \leq k \leq n - 1, 1 \leq i \leq 9)$
\sum_{k=0}^{n-1} \sum_{i=1}^{9} i \times 10^k \times \frac{c_{i} \times (n - 1)!}{c_{1}!c_{2}!c_{3}!c_{4}!c_{5}!c_{6}!c_{7}!c_{8}!c_{9}!}
ある数 $c_{i}$ を分子にかけておくことで、分母の $c_{i}!$ と約分が起き、分子が $(c_{i}-1)!$ となります。
このままでは式が複雑なので、シグマをバラして見ましょう。以下の公式を用います。
\sum_{i=1}^{n} \sum_{j=1}^{n} ij = \sum_{i=1}^{n} i \sum_{j=1}^{n} j
このような問題は過去に AtCoder で出題されているので興味のある方は解いてみて下さい。
ではこの公式を利用して先ほどの式をわかりやすくしてみましょう。
\sum_{k=0}^{n-1} \sum_{i=1}^{9} i \times 10^k \times \frac{c_{i} \times (n - 1)!}{c_{1}!c_{2}!c_{3}!c_{4}!c_{5}!c_{6}!c_{7}!c_{8}!c_{9}!} \\
= (n-1)! \sum_{k=0}^{n-1} 10^k \sum_{i=1}^{9} i \times c_{i} \sum_{j=1}^{9} \frac{1}{c_{j}!} \\
= (n-1)! \frac{10^n - 1}{9} \sum_{i=1}^{9} i \times c_{i} \sum_{j=1}^{9} \frac{1}{c_{j}!}
かなり簡潔になりましたね！
等比数列の和の公式なども使用しているので理解出来なかったは以下の記事を参考にしてみて下さい。
このようにすれば、かなり高速求めることができました。
逆元が必要になるのでフェルマーの小定理より Python の pow関数 を使用してコードを書いていきます。
ACコード
n = int(input())
c = list(map(int, input().split()))
mod = 10 ** 9 + 7
# 階乗テーブル
fac = [1] * (n + 1)
for i in range(n):
fac[i + 1] = fac[i] * (i + 1)
fac[i + 1] %= mod
# 10^kの和
t = (pow(10, n, mod) - 1) * pow(9, -1, mod)
# i * Ci の和
i_Ci = 0
for i in range(9):
i_Ci += (i + 1) * c[i]
# 1 / (c1! * c2! * ... * c9!) の積
fac_Ci = 1
for i in range(9):
if fac[c[i]] == 0: continue
fac_Ci *= pow(fac[c[i]], -1, mod)
ans = t * i_Ci * fac_Ci * fac[n - 1] % mod
print(ans)
最後に
最後まで読んできただきありがとうございました！
これから数学問題を中心に記事を上げていこうかと思っています。
リクエストなどがあればぜひ声かけて下さい！ありがとうございました！