読者です 読者をやめる 読者になる 読者になる

yukicoder #503: 配列コレクション

操作回数をa, 最後に残る要素の数をbとする。
N>=Kよりa>=1
K>=2よりb>=1

最終的にAの各要素はDの累乗になることがわかる。
D=1のとき、コーナーケースでAのすべての要素は1になるので解は
b

以下、D≠1とする。
Aの要素はDの累乗であり、かつ操作回数がaなので、取りうる値は
1,D,D^2,...,D^a
のいずれかである。

ここでD^aまでというのをきちんと説明する。
操作はa回である。操作1回で掛けられるDは1個だけ増える。というのはB[i]=D^tとして、このt回分は以前の
操作の分であるため。よって、全体でDがa回掛けられていることがわかる。また、このa個は1箇所に集めることができる。すなわち必ずD^aを作れる。更に、それは任意の箇所で可能。

D^k (0<=k<=a) について考える。
D^aにかぎらず、D^kは任意の箇所に作れる。
D^kをすべて数えてみよう。

そうすれば解はΣ(D^k*(D^kの出現回数))で求まる。
D^kは任意の箇所に作れるのでその場所はb通り。
その1通りに対して、数列の残りの部分を決めていく。
残りはb-1箇所であった。
更に、残りa-k個のDをb-1箇所のいずれかに掛けて行く必要がある。
つまり、b-1箇所から重複を許してa-k個を選ぶ事になり、これは単に
H(b-1, a-k)
で求まる。
したがって、解は
Σ(D^k * b * H(b-1, a-k))
である。

実は今のところにコーナーケースがある。
残りb-1箇所からa-k個を重複を許して選ぶと言った。ところが、b-1=0の場合はH(b-1,a-k)の計算がうまくできない。
なのでb=1がコーナーケースになる。
式で見れば
H(b-1,a-k)
=C(a+k+b-2,a-k)
a-k+b-2<a-kとすると
b-2<0
b<2
b>=1より
b=1
b=1というのは配列がただ1個の要素しか持たないので解は
D^k