941 Permutations

題目說明

題目會給n筆測資，每筆測資兩行，第一行是一個字串，代表一個字元的序列，第二行是一個整數m，代表康托編碼的第m次的序列(即next_permutation的第m次迴圈的序列) 而next_permutation的邏輯是在比當前序列還大的序列中最小的序列

解題思路

因為題目測資達到了20!，所以不能直接用next_permutation找，只能使用康托逆運算 也就是將康托編碼的邏輯反過來，求出該序列是第幾次的next_permutation 而康托逆運算的方法如下: 假設我有個序列{0,1,2,3,4,5,6}(長度為7) 他的第69個排列就是: 69/6!=0，第0位就是取第0小的數字(即為0)，然後將0從{0,1,2,3,4,5,6}取出，序列變為{1,2,3,4,5,6} 69/5!=0，第1位就是取第0小的數字(即為1)，然後將1從{1,2,3,4,5,6}取出，序列變為{2,3,4,5,6} 69/4!=2，第2位就是取第2小的數字(即為4)，然後將4從{2,3,4,5,6}取出，序列變為{2,3,5,6}，然後將69取餘數4!變為21 21/3!=3，第3位就是取第3小的數字(即為6)，然後將6從{2,3,5,6}取出，序列變為{2,3,5}，然後將21取餘數3!變為3 3/2!=1，第4位就是取第1小的數字(即為3)，然後將3從{2,3,5}取出，序列變為{2,5}，然後將3取餘數2!變為1 1/1!=1，第5位就是取第1小的數字(即為5)，然後將5從{2,5}取出，序列變為{2}，然後將1取餘數1變為0 0/0!=0，第6位就是取第0小的數字(即為2)，然後將2從{2}取出，序列空，將0取餘數1變為0 這樣下來，第69位序列就是{0,1,4,6,3,5,2}了

程式碼

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
void counting(vector<char>& nums, long long m) {
  vector<char> result;
  vector<long long> fact(nums.size());  // 儲存階乘用的
  fact[0] = 1;
  for (int i = 1; i < nums.size(); ++i) fact[i] = fact[i - 1] * i;
  for (int i = nums.size() - 1; i >= 0; --i) {  // 康托逆運算
    long long f = fact[i];
    int idx = m / f;
    m %= f;
    result.push_back(nums[idx]);
    nums.erase(nums.begin() + idx);
  }
  nums = result;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    string N;
    cin >> N;
    sort(N.begin(), N.end());
    vector<char> ans;
    for (char i : N) ans.push_back(i);
    long long m;
    cin >> m;
    counting(ans, m);
    for (char x : ans) cout << x;
    cout << endl;
  }
  return 0;
}