F. Multiplicative Arrays
こたつがめさんの放送の振り返りを見てAC。理解した後でも難しい気がするが……。
二項係数でどうにかする問題というのは分かるが、そこで止まってしまった。
たとえば、k=6でn=4のときの場合の数は、2を入れる位置と3を入れる位置を考えて、4*4となる。なので、n以下のを足し合わせる場合、4*4+3*3+2*2+1*1＝30となる。
……のように考えて、上手くいかなかった。
このように考えるのではなく、数字を入れる箇所を何個にするか？ と考えると二項係数の和になり高速化できる。
先程の6の場合だと、[6], [2, 3], [3, 2]の三通りがある。
[2, 3]の順で入れるとすると、Combi(4, 2)通り。n=3, 2, 1の場合を考えると、Combi(3, 2), Combi(2, 2), 0通りとなり、その和は（公式により）Combi(5, 2)と計算できる。
単純に素因数分解するのではなく、何をどういう順番で掛け合わせてkにしたか？ と考えなくてはいけなかった。
0 件のコメント:
コメントを投稿