C - N!÷K番目の単語 解説 by miscalculation53
階乗進法を利用した考察公式解説と本質的には同じですが、階乗進法 を経由した考察を紹介します。
[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\) に注意してください)
投稿日時:
最終更新: