[競技プログラミング,競プロ解説]
- まず最初に、この問題は数え上げの対象が因数ごとに独立であることが理解できていないとイメージがつかめないと思う
- そういう文脈では、確率の期待値の線形性に似ている
- 頭が悪いので抽象的に考えられない
- N=3, M=12の場合を考える。Mを因数分解すると、M={2^2, 3}
- このとき対象の数列のサイズは3、3要素に因数ごとの数値を割り当てるイメージ
- この割り当ては大学受験でやった人も多いかもしれない、重複組合せである
- 異なるｎ個のものから重複を許してｒ個とってくる組合せの総数を
と書く
- 異なるｎ個の数列の場所から重複を許して因数を割り当てる組合せの総数
- 2^2 = {2,2} を割り当てると...?
- 6通り (= 3H2 -> 3+2-1C2 -> 4*3/2 -> 6)
| _ |
_ |
_ |
| {2,2} |
{} |
{} |
| {} |
{2,2} |
{} |
| {} |
{} |
{2,2} |
| {2} |
{2} |
{} |
| {2} |
{} |
{2} |
| {} |
{2} |
{2} |
- 3 = {3} を割り当てると...?
- 3通り (= 3H1 -> 3+1-1C1 -> 3/1 -> 3)
| _ |
_ |
_ |
| {3} |
{} |
{} |
| {} |
{3} |
{} |
| {} |
{} |
{3} |
- それぞれの因数は独立なので、上の表の１行に対して下の表がある→総数は6×3通り＝18通り
- なお、組み合わせの数え上げ実装には階乗のmod逆元 - 組み合わせを使う、ハードだなあ…