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

順列と数を一対一に対応させるテクとして階乗進数というものが知られている。

階乗進数というのは次のような数の表現方法。

$$ n = \sum_{k=1}^{N-1} a_k \cdot k! \quad (0 \le a_k \le k) $$

辞書順で n 番目の順列は、n を階乗進数で表した時の各桁を使って構成できる。そのため、(n!-1)/k の階乗進数表現がわかれば答えを出せる。これは

$$ n!-1 = (1, 2, 3, 4, \ldots, n-2, n-1) $$

を k で割れば求められる。k で割るのは筆算と同じ要領で O(n) で可能。筆算の方法はコードを見てください。

復元は BIT をゴニョるのが多分楽。

（補足：2016/1/20）

n!/k - 1 の階乗進数表現を求める方が素直な方法だと思います。解説に書いた方法では $n!/k - 1=\lfloor (n! - 1)/k \rfloor$ になることを用いて、-1 をする手間を省きました。

yukicoder で Factorial number system という概念を見かけていたので解けた。