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; }