AtCoder Regular Contest 047 C - N!÷K番目の単語

お題箱より。

解法

※この解説の「何番目」という表記は全て1-indexedです。

一般に $n$ を $1$ 以上 $N!$ 以下の整数として、 $N!$ 個の順列のうち辞書順で $n$ 番目にあるものを、前の要素から順番に求めていく方法を考えます。

最初の要素は、 $N!$ 個の順列を辞書順に並べて $N$ 等分したグループに分けたときに、対象の順列が何番目のグループにあるかで決まります。
次の要素は、対象の順列が属していたグループをさらに $(N-1)$ 等分したグループに分けたときに、対象の順列が何番目のグループにあるかで決まります。
…

この手順を繰り返すことで対象の順列を求めることができます。 $i$ 段階目の手順で属しているグループが $g_{i}$ 番目だとすると、対象の順列の $i$ 番目の要素は、それまで使われていない正の整数のうち小さい方から $g_{i}$ 番目のものです。

f:id:betrue12:20210221130509p:plain

今回求めたいのは $\frac{N!}{K}$ 番目の順列です。各段階で何番目のグループに属するかを求めるには割り算の商、そのグループ内で何番目の順列であるかを求めるには割り算の余りとして計算できますが、桁数が非常に大きいので直接計算することは困難です。

ここからの考え方の概要をまず示します。先ほどの図で示した1つ1つの段階において、全体のサイズを $1$ とするような相対値として、対象の順列の位置を管理します。そして属しているグループが何番目かを求めて、そのグループのサイズがまた $1$ となるように「拡大」して、次に属しているグループが何番目かを求めて…ということを繰り返していきます。

具体的な手順を説明します。まず $N!$ 個の順列全体のサイズを $1$ と見なすと、最初の順列の位置は $\frac{1}{N!}$ 、最後の順列の位置は $\frac{N!}{N!}$ すなわち $1$ です。そして対象の順列の位置は $\frac{1}{K}$ だと見なすことができます。