Official
H - Next Permutation Editorial by toam
\(N\) の順列のうち，辞書順で \(P\) が（0-indexed で（以下同様）） \(x\) 番目に， \(Q\) が \(y\) 番目に小さいとします．このとき，求める順列は \((y-x\pmod{N!})\) 番目に小さい順列です．
ここで，正整数 \(K\) を階乗進数表示すると，辞書順で \(K\) 番目に小さい順列を求めることができます．逆に，順列が辞書順で \(K\) 番目に小さいとすると，順列から階乗進数表示された \(K\) も求めることができます．
変換方法
$N=5$ において，$23110_{(!)}$ 番目に小さい順列 $P$ は次の手順によって求められます．- $\lbrace 1,2,3,4,5\rbrace$ の中で（0-indexed で） $2$ 番目に小さいものは $3$ より $P_1=3$
- $\lbrace 1,2,4,5\rbrace$ の中で $3$ 番目に小さいものは $5$ より $P_2=5$
- $\lbrace 1,2,4\rbrace$ の中で $1$ 番目に小さいものは $2$ より $P_3=2$
- $\lbrace 1,4\rbrace$ の中で 1$$ 番目に小さいものは $4$ より $P_4=4$
- $\lbrace 1\rbrace$ の中で $0$ 番目に小さいものは $1$ より $P_5=1$
- 以上により $P=(3,5,2,4,1)$ である．
- $\lbrace 1,2,3,4,5\rbrace$ の中で $3$ は（0-indexed で） $2$ 番目に小さいから，$K$ の $4!$ の位の数字は $2$
- $\lbrace 1,2,4,5\rbrace$ の中で $5$ は $3$ 番目に小さいから，$K$ の $3!$ の位の数字は $3$
- $\lbrace 1,2,4\rbrace$ の中で $2$ は $1$ 番目に小さいから，$K$ の $2!$ の位の数字は $1$
- $\lbrace 1,4\rbrace$ の中で $4$ は $1$ 番目に小さいから，$K$ の $1!$ の位の数字は $1$
- $\lbrace 1\rbrace$ の中で $1$ は $0$ 番目に小さいから，$K$ の $0!$ の位の数字は $0$
- 以上により $K=23110_{(!)}$ である．
さらに，階乗進数表示された \(2\) つの数の加算を階乗進数表示上で行うこともできます（通常の筆算と同様に下の桁から計算すればよいです）．
よって，以下の手順で答えを求めればよいです．
- \(N!-x\) を階乗進数で求める（これは， \(N!-x-1\) 番目に小さい順列は \(R_i=N+1-P_i\) として得られる順列 \(R\) であることを利用して求められる）．
- \(y\) を階乗進数で求める．
- \(y-x \pmod{N!}\) を階乗進数で求める．
- \((y-x \pmod{N!})\) 番目に小さい順列を求める．
順列を階乗進数に変換したり，階乗進数を順列に変換するためには，集合に対して
- 要素の追加・削除
- 集合の要素のうち \(k\) 番目に小さい要素を求める
- 集合のある要素が集合の中で何番目に小さいかを求める
が高速にできるデータ構造があればよく，これは fenwick tree などを用いて行えます．計算量は \(O(N \log N)\) です．
posted:
last update: