自分のための解法メモ (公式の解法スライド読んでピンとこなかったので)
問題: C - N!÷K番目の単語
今回は、番目の数字において、その時点で残っている数字のうち、小さい方から何番目の数字を使うかを表すインデックス(0-indexed)を計算する。
1つ目の数字のインデックスはにおけるである。
(は整数で、)
それぞれの値を計算すると、以下のようになる。 (はAをBで割ったあまりとする)
ここで、とすると、と表せる。
次に、2つ目の数字(のインデックス)はの値を利用し計算できる。
のとして計算できる。(は整数で、)
各値を計算すると以下のようになる。
このとき、とすると、と表せる。
同様に計算していくと、番目のインデックスは以下のように表せることが分かる。
ここで解のために必要となる値はであり、大きい値になるを計算せずにを計算するだけで済むのがポイント。
今回必要となるBIT上のlower boundは1回で計算できる。
以下が参考になった。
http://hos.ac/slides/20140319_bit.pdf
あと、ここで計算できるのは辞書順で番目 (0-indexed)のインデックスであるため、辞書順において1つ前のインデックスを計算する必要があるが、デクリメント的に計算できる。
今回書いたコード。計算量は。
Submission #2099468 - AtCoder Regular Contest 047
N, K = map(int, input().split()) # BIT data = [0]*(N+1) def get(k): s = 0 while k: s += data[k] k -= k & -k return s def add(k, x): while k <= N: data[k] += x k += k & -k # BIT上のlower bound def lower_bound(w): i = 0; s = 0 k = 2**(N.bit_length()-1) while k > 0: if i + k <= N and data[i + k] < w: w -= data[i + k] i += k k >>= 1 return i+1 # 各インデックスを計算 a = 1 res = [] for i in range(N): m = (N-i)*a // K res.append(m) a = ((N-i)*a) % K add(i+1, 1) # 計算したのはN!/K (0-indexed)であるため、インデックスを1戻す idx = N-1 while res[idx] == 0: res[idx] = N-1-idx idx -= 1 res[idx] -= 1 # 各インデックスに対応する数字をBITから求める ans = [] for i in res: idx = lower_bound(i+1) add(idx, -1) ans.append(idx) print(*ans, sep='\n')
こういうシンプルな問題、手の付け方が難しい。