【解説記事】Atcoder Regular Contest 047 ~N!÷K番目の単語~

# 問題
$1 \sim N$ の整数を並べ替えてできる順列のうち，辞書順で$\frac{N!}{K}$ 番目の順列を求め，先頭から順に出力せよ．
ただし，整数$K$は$N$以下の正の整数とする．

*制約*

```math
1 \leq K \leq N \leq 10^5
```

https://atcoder.jp/contests/arc047/tasks/arc047_c

# 導入
以下ではみやすさのために，1, 2, 3...をA, B, C...で置き換えて表記している．
また，$v_1 = \frac{N!}{K}$ とし，以下の関数を定義する．

```math
m(x) = \left\{
\begin{array}{ll}
x \% K & (x \% K \neq 0) \\
K & (その他)
\end{array}
\right.
```


# 1文字ずつ求める
入力例1 ($N = 4, K = 3$) を例に説明を行う．
このとき，求めるべき順列は $\frac{4!}{3} = 8$番目の順列である．

全ての整数を同時に求めるのは難しいので先頭から求めることを考える．
順列は辞書順に並んでいるので，先頭の1文字を固定するとその1文字を先頭とする文字列は$(N - 1)!$通り存在することがわかる．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355593/f906f81a-3655-415e-fa82-db572eda0acb.png)


つまり，1文字目は$x_1 = {\rm ceil}\biggl(\frac{v_1}{(N - 1)!}\biggl)$であることがわかる．

# 2文字目を求める
例えば，例ではBを1文字目として固定するので，Aを1文字目として固定したときの順列の個数を引くことによって，Bを1文字目とした順列を先頭とした順序に変更できる．
Cを1文字目とした場合はAとBを1文字目としたときの順列の個数，つまり，$2 \times (N - 1)!$を引く．
同様に先頭文字が$x_1$番目の文字であったときのことを考えると$v_0$ から $(x_1 - 1) \times (N - 1)!$を引けば，$x_1$番目の文字を１文字目とした順列を先頭とした順序に変更できる．
よって，2文字目を固定したときに得られる順列は1文字目を固定したときに得られる順列の前から $v_2 = v_1 - (x_1 - 1) \times (N - 1)!$番目の順列である．

また，2文字目までを固定したときに残りの並べ替え方は$(N - 2)!$通り存在する．
したがって，既に固定されている1文字目以外の $N - 1$ 文字の内，$x_2 = {\rm ceil}\biggl(\frac{v_2}{(N - 2)!}\biggl)$番目の文字が2つ目に固定される文字である．

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/355593/5a1095c5-4823-635b-e6d1-c3fd4062e621.png)

# i + 1番目の文字を求めるための一般化
1文字目と2文字目の議論を一般化すると，$i$番目の文字まで固定し， $i + 1$番目の文字を求めることを考える．
前述の記号と同様に，求めたい順列が現在までに固定した文字は固定し，それ以外の文字を並べ替えたときに得られる順列の内，$v_{i+1}$ 番目の順列であるとし，$i + 1$番目に固定する文字は固定されていない文字の内，$x_{i+1}$番目の文字であると仮定する．

すると，$v_i$と$x_i$の漸化式はそれぞれ

```math
v_{i + 1} = v_i - (x_i - 1) \times (N - i)! \\
x_{i + 1} = {\rm ceil}\biggl(\frac{v_{i + 1}}{(N - (i + 1))!}\biggl)
```

となる．

# 漸化式の計算方法
制約上の問題から，64bit整数であっても，$N!$を計算することはできない．
したがって，何らかの工夫をして計算する必要がある．

$v_i$ は$O(N!)$であり，Overflowしてしまい計算することはできないが，$x_i$は計算可能であることに着目する．
$1 \leq v_{i + 1} \leq (N - i)!$ (並べ替える文字数が$N - i$文字であるため)であるから，

```math
v_1 = \frac{N!}{K} \\
x_1 = {\rm ceil}\biggl(\frac{N}{K}\biggl) \\
v_2 = \frac{N!}{K} - (x_1 - 1) \times (N - 1)! = \frac{m(N)}{K} (N - 1)! \\
x_2 = {\rm ceil}\biggl(\frac{m(N)}{K} \frac{(N - 1)!}{(N - 2)!} \biggl) = {\rm ceil}\biggl(\frac{m(N)}{K} (N - 1) \biggl) \\
v_3 = \frac{m(N)}{K} (N - 1)! - (x_2 - 1) \times (N - 2)! = \frac{m(N (N - 1))}{K}(N - 2)! \\
x_3 = {\rm ceil}\biggl(\frac{m(N (N - 1))}{K}\frac{(N - 2)!}{(N - 3)!}\biggl) = {\rm ceil}\biggl(\frac{m(N (N - 1))}{K}(N - 2)\biggl)
```

ここで利用した$m(x)$ は導入において定義した関数である．
また，途中計算式は省略しているものの，上述の$v_i$の制約と $((x \% K) \times y) \% K = (x \times y) \% K$ の関係式から上のような式が少なからず$i = 3$までは成立する．

証明はつけないが，上記の関係式は一般に成立するため，$x_i$を求めるためには${\rm ceil}\biggl(\frac{m(N(N - 1)...(N - i + 2))}{K} \times (N - i + 1) \biggl)$を求めれば良いことがわかる．

上記の式は$N$回ループで$i = 1, 2, ..., N$の全てに対して計算可能である．
したがって，各 $i$ に対して，残っている文字の内，何番目の文字を出力すればよいか，はこれによって解答可能であり，計算量は$O(N)$となる．

あとは残っている文字の内，K番目の要素を取得するデータ構造を利用すれば良い．

# SetのK番目の要素を取得する方法
典型なので他の記事の参照をつける．

サイズ$N$のBinary Indexed Treeを取り，各Indexに対応する値が1のときはそのIndexの要素がSet内に存在する，0のときは存在しないというように定義する．
すると，$1 \sim x$番目の要素までの和を取ったときに$K$以上となるような$x$の内，最も小さな$x$が求めるべき$x$であることがわかる．
これはBinary Indexed Treeに下限の二分探索を導入することで実現可能となる．

[k 番目の値を高速に取り出せるデータ構造のまとめ - BIT上二分探索や平衡二分探索木など](https://qiita.com/drken/items/1b7e6e459c24a83bb7fd)
[k 番目に小さい値を取得可能な集合を管理するデータ構造](https://kazuma8128.hatenablog.com/entry/2018/06/20/210631)

# 実装 (C++)
全体を通した計算量は$O(N(log N)^2)$となり十分高速．
[自分の提出](https://atcoder.jp/contests/arc047/submissions/16031840)

以下の実装ではBinary Indexed Treeは0-indexedであることに注意．

```c++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct BinaryIndexedTree{
    int n, M; vector<int> dat;
    BinaryIndexedTree(ll n): dat(n + 1), n(n){M = 1; while (M <= n) M <<= 1;};
    int query(int i){
        // 0-indexed: a[0] + a[1] + ... + a[i - 1] + a[i]
        int ret = 0;
        for (int j = i; j >= 0; j = (j & (j + 1)) - 1) ret = ret + dat[j];
        return ret;
    }

    int lower_bound(int key){
        int left = 0, right = M;
        for (int i = right; i > 0; i /= 2)
            if (left + i <= n && dat[left + i - 1] < key)
                key -= dat[left + i - 1], left += i;
        return left;
    }

    void update(int i, int v){for(int j = i; j < n; j |= j + 1) dat[j] = v + dat[j];}
};

ll ceil(ll numerator, ll denominator){return numerator % denominator ? numerator / denominator + 1 : numerator / denominator;}
ll moduloK(ll x, ll k){return x % k ? (x % k) : k;}

int main(void){
    int n, k; long long numerator; cin >> n >> k;
    BinaryIndexedTree bit(n + 1);
    for (int i = 0; i < n; i++) bit.update(i + 1, 1);

    numerator = n;
    for (int i = 0; i < n; i++){
        int ans = bit.lower_bound(ceil(numerator, k));
        numerator = moduloK(numerator, k) * (n - 1 - i);
        bit.update(ans, -1);
        printf("%d\n", ans);
    }
    return 0;
}

```

# あとがき
この問題はFactorial Number Systemもしくは階乗進数と呼ばれる考え方の問題．
上記の説明における，$x_i$を用いて，ある正の整数$M (\leq N! - 1)$ を $M = \sum_{i = 1}^{N} (x_i - 1) \times (N - i)!$と表すことができる．
このような形で各$i$に対する階乗値を基底に取り，正の整数を基底分解した記法を階乗進数記法と呼ぶ．
上述した通り，この記法において，$0 \leq x_i - 1 \leq i - 1$である．