公式解説と本質的には同じですが、階乗進法 を経由した考察を紹介します。

[1] 階乗進法とは

階乗進法は、位取り記数法の各桁の重みを階乗にしたものです。つまり、整数 \(X\) を

\[X = a_{N-1} \cdot (N-1)! + a_{N-2} \cdot (N-2)! + \cdots + a_2 \cdot 2! + a_1 \cdot 1! + a_0 \cdot 0!\]

の形で表す方法です。ここで、\(a_i\) の値の範囲を \(0 \leq a_i \leq i\) に制限すると、\(N!\) 通りの数列 \((a_0, a_1, \ldots, a_{N-1})\) と \(0\) 以上 \(N!\) 未満の値 \(X\) が一対一対応する（すなわち、階乗進法による表現方法が一意である）ことが証明できます。

たとえば、\(10 = 1 \cdot 3! + 2 \cdot 2! + 0 \cdot 1! + 0 \cdot 0!\) と表現できます。これを \(10 = 1200_{(!)}\) とも書くことがあります。

後述するように、「整数 \(X\) の階乗進法による表現」と、「長さ \(N\) の順列のうち辞書順で \(X\) 番目に小さいもの」の間には対応があります。そこで、

• まず \(\frac{N!}{K}\) を階乗進法で表し、
• そこから \(\frac{N!}{K}\) 番目の順列を得る

という方針を考えることができそうです。

[2] \(\frac{N!}{K}\) の階乗進法での表現

\(\frac{N!}{K}\) の階乗進法での表現は、割り算の筆算のようにして得ることができます。

\(\frac{5!}{3}\) での計算例を次に示します。（便宜上、\(a_i \leq i\) という制限を一旦取り払っている部分があります）

\[\begin{array}{lrlr} & 12200_{(!)} \\ 3) \! \! \! \! \! \! \! \! & \overline{100000_{(!)}} & = & 50000_{(!)} \\ & 30000_{(!)} & \\ & \overline{20000_{(!)}} & = & 8000_{(!)} \\ & 6000_{(!)} \\ & \overline{2000_{(!)}} & = & 600_{(!)} \\ & 600_{(!)} \\ & \overline{00_{(!)}} \end{array}\]

一般の場合でも同じように求めることができて、計算量は \(O(N)\) です。

[3] 階乗進法から順列への変換

\((0, 1, \ldots, N-1)\) の順列のうち、（0-indexed で）\(X\) 番目の順列は、\(X\) の階乗進法での表現から求めることができます（参考：レーマー符号）。具体的には、求める順列を \(P = (P_0, P_1, \ldots, P_{N-1})\) 、\(X\) の階乗進法での表現を

\[X = a_{N-1} \cdot (N-1)! + a_{N-2} \cdot (N-2)! + \cdots + a_2 \cdot 2! + a_1 \cdot 1! + a_0 \cdot 0! \quad (0 \leq a_i \leq i)\]

とすると、次のようにして前から求められます。

• \(P_0\) は \(a_{N-1}\) である。
• \(P_1\) は \(P_0\) 以外の候補のうち（0-indexed で）\(a_{N-2}\) 番目に小さいものである。
• \(P_2\) は \(P_0, P_1\) 以外の候補のうち（0-indexed で）\(a_{N-3}\) 番目に小さいものである。
• \(\vdots\)
• \(P_i\) はここまでで \(P\) に使っていない候補のうち（0-indexed で） \(a_{N-1-i}\) 番目に小さいものである。
• \(\vdots\)

このような処理は Fenwick Tree (Binary Indexed Tree) 上の二分探索によって行うことができ、計算量は \(O(N \log N)\) です。

なお、0-indexed では求めるものは \(\frac{N!}{K} - 1\) 番目であることには注意が必要です。階乗進法表現上で \(-1\) してもよいですし、順列を求めてから prev_permutation 等を用いてもよいです。（後者の場合、\(K = 1\) に注意してください）