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 <iostream>
#include <vector>
#include <algorithm>
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;
}