読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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

AtCoder BIT

問題

arc047.contest.atcoder.jp

解法

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

thilogane.hatenablog.com

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

$$ 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 をゴニョるのが多分楽。

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


(補足:2016/1/20)

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

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