题解 | 奶牛排排站

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
const int N=25;
int fac[N];
void init_fac()
{
    fac[0]=1;
    for(int i=1;i<N;i++)
    {
        fac[i]=fac[i-1]*i;
    }
}

int kt(vector<int> &a)
{
    int res=0;
    vector<bool> used(N,false);
    for(int i=0;i<n;i++)
    {
        int ans=0;
        for(int j=1;j<=n;j++)
        {
            if(!used[j]&&j<a[i])
            {
                ans++;
            }
        }
        res+=ans*fac[n-1-i];
        used[a[i]]=true;
    }
    return res+1;
}

vector<int> inv_kt(int pos)
{
    vector<int> res;
    vector<bool> used(n+1,false);
    pos--;
    for(int i=0;i<n;i++)
    {
        int m=n-i-1;
        int ans=pos/fac[m];
        for(int j=1;j<=n;j++)
        {
            if(!used[j])
            {
                if(ans==0)
                {
                    used[j]=true;
                    res.push_back(j);
                    break;
                }
                ans--;
            }
        }
        pos%=fac[m];
    }
    return res;
}

signed main()
{
    init_fac();
    cin>>n>>k;
    while(k--)
    {
        char op;
        cin>>op;
        if(op=='P')
        {
            int A;
            cin>>A;
            vector<int> ktA;
            ktA=inv_kt(A);
            for(int c:ktA)
            {
                cout<<c<<' ';
            }
            cout<<endl;
        }
        else
        {
            vector<int> B(n);
            for(int i=0;i<n;i++)
            {
                cin>>B[i];
            }
            cout<<kt(B)<<endl;
        }
    }
}