题解 | 奶牛排排站

这样考虑：长度为N的排列有N!种全排列。那么长度为N-1的排列有（N-1）!种全排列。那么对于长度为N的排列，第一项为1时有（N-1)!种排列方式，第一项为2时也是(N-1)!种，一直到第一项为n，一共n*(N-1)!种，按字典序升序。那么模拟出每一项是多少即可。假如选定第一项是2，那么后N-1项也是互不相同的数字，可以当成一个排列，之后选定数字为'k'时应是当前备选数字的第k小数字。如此即可模拟出答案。

这里选用set维护备选数字集合。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N,K;
    cin>>N>>K;
    long long fracs[21];
    fracs[0] = 1;
    fracs[1] = 1;
    for(int i=2;i<=20;i++)fracs[i] = fracs[i-1]*i;
    while(K--){
        set<int>st;
        for(int i=1;i<=N;i++)st.insert(i);
        string s;cin>>s;
        if(s[0]=='P'){
            long long x;cin>>x;
            int now = N-1;
            auto it = st.begin();
            while(now>=0){
                while(x>fracs[now]){it++;x-=fracs[now];}
                cout << *it << " ";
                st.erase(it);
                it = st.begin();
                now--;    
            }
        }
        else{
            long long ans = 1;
            auto it = st.begin();
            for(int i=N-1;i>=0;i--){
                int x;cin>>x;
                while(*it != x){
                    it++;
                    ans += fracs[i];
                }
                st.erase(it);
                it = st.begin();
            }
            cout << ans;
        }
        cout << endl;
    }
}
// 64 位输出请用 printf("%lld")