mayoko’s diary

プロコンとかいろいろ。

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

解法

まず, X 番目の順列がどのような順列になるのか, という問題を考えてみます。

並べる数が 0-index であるとすると, 一番最初の数は X/(N-1)! で与えられます(X < (N-1)! だったら最初の数は 0, X == (N-1)! だと最初の数は 1, ... のようになります)。
これは N-1 最初の数を決めて残りの N-1 個の数の並べ方が (N-1)! 通りであることから明らかです。

で, X を (N-1)! で割った余りが Y であるとすると, 次の数は Y/(N-2)! で与えることが出来ます。以下同様です。

部分点解法では, これを愚直にやれば答えを得られます。(20! はギリギリ long long の範囲を超えないので C++ でも大丈夫な気がします)

満点解法では, N の値が大きいためにそのままやるだけではできず, 工夫する必要があります。上の解法ではある数を 「(N-i)! で割った商を求める」という作業と, 「(N-i)! で割った余りを求める」という作業が要求されていますが, これをうまく計算したいです。

まず N!/K を (N-1)! で割った余りを求めることを考えてみます。
N!/K = N/K * (N-1)! であり, N = a*K + b であるとすると,

N/K * (N-1)! = a*(N-1)! + (b/K) * (N-1)! となり, 結局 N!/K を (N-1)! で割ったあまりは b = N%K について, b/K*(N-1)! を計算して それを (N-1)! で割ったあまりと等しくなります。

例を挙げると, 例えば 4!/3 を 3! で割った余りを求めたい時, 4%3 = 1 より, 1/3* 3! を 3! で割ったあまりに等しくなります。これは 2 になりますね(実際 4!/3 = 8 を 3! で割った余りは 2 です)。

実際に考えるときは, b/K * (N-1)! という値を保持しておくことは出来ませんが, b だけを保持しておくことは出来ます。b の値を持っておくと, b/K * (N-1)! を (N-2)! で割った商(これが求める順列の 2 番目の数を小さい方から数えた時の数になります)は, b/K*(N-1) で求められます((N-1)!/(N-2)! = N-1 より)。

こんな感じで割ったあまりと商を管理することで, 各数を小さい方から数えた時に何番目になるかを求められます。あとは BIT とかを使って実際に値を得れば良いです。K=1 の時に BIT でやると不幸になりました。

// 0-based Binary Indexed Tree
// 数え上げ用
constexpr int mod = 1e9+7;
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s += bit[i]) %= mod;
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] += x) %= mod;
            i += i&-i;
        }
    }
    // [a, b]
    T sum(int a, int b) {
        return sum(b+1)-sum(a);
    }
    // sum(0, i) >= wとなる最小のiを求める 存在しなければmaxを返す
    int lb(T w) {
        if (w <= 0) return 0;
        int k = 1;
        while (k <= max) k <<= 1;
        int i = 0;
        for (; k > 0; k >>= 1) if (i+k <= max && bit[i+k] < w) {
            w -= bit[i+k];
            i += k;
        }
        return i+1;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, K;
    cin >> N >> K;
    if (K == 1) {
        for (int i = 0; i < N; i++) {
            cout << N-i << endl;
        }
        return 0;
    }
    BIT<int> bit(N);
    for (int i = 0; i <= N; i++) bit.add(i, 1);
    vector<int> ans(N);
    ll rest = 1;
    for (int i = 0; i < N; i++) {
        ll tmp = rest*(N-i);
        rest = tmp%K;
        tmp /= K;
        int low = 0, high = N+1;
        while (low < high) {
            int med = (high+low)/2;
            if (bit.sum(med) <= tmp) low = med+1;
            else high = med;
        }
        ans[i] = low-1;
        bit.add(low-1, -1);
    }
    prev_permutation(ans.begin(), ans.end());
    for (int i = 0; i < N; i++) {
        cout << ans[i]+1 << endl;
    }
    return 0;
}