本番は出ていたけど少し覗いただけで、Bに時間を取られて(結局解けなかった)触れなかった問題。 こちらをやっていれば解けていたかもしれない。

C - N!÷K番目の単語

問題

階乗進数。$O(N)$。

$\frac{1}{K}\cdot N! - 1$の階乗進数表記を求める問題。 連分数展開の要領で整数に直していく。

$\frac{1}{K} \cdot N! = \frac{N}{K} \cdot (N-1)! = \lfloor \frac{N}{K} \rfloor \cdot (N-1)! + \frac{(N \bmod K)(N - 1)}{K} \cdot (N-2)! = \dots$

実装

math.gcdはversion 3.5かららしい。REした。

#!/usr/bin/env python3
def math_gcd(a, b):
    a, b = min(a, b), max(a, b)
    while a > 0:
        a, b = b % a, a
    return b
# input
n, k = map(int,input().split())
# make factoradic number 1/k*n!
ds = [0] * n
p, q = 1, k
e = n
while e-1 >= 1:
    p *= e
    e -= 1
    ds[e] = p // q
    p %= q
    r = math_gcd(p, q)
    p //= r
    q //= r
# decrement
for i in range(n):
    if ds[i]:
        ds[i] -= 1
        break
    else:
        ds[i] = i
# decode factoradic
cs = list(range(1,n+1))
for d in reversed(ds):
    print(cs[d])
    del cs[d]