Luogu P3014 [USACO11FEB]牛線Cow Line

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
#define
ll cantor(int *a, int n) {
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll x = 0; int c = 1; ll m = 1;
        for (int j = i + 1; j <= n; j++) {
            if (a[j] < a[i]) x++;
            m *= c; c++;
        }
        ans += x * m;
    }
    return ans;
}
ll fac[21];
void decantor(int x, int n) {
    vector<int> v, a;
    for (int i = 1; i <= n; i++) v.push_back(i);
    for (int i = n; i >= 1; i--) {
        int r = x % fac[i - 1];
        int t = x / fac[i - 1];
        x = r;
        sort(v.begin(), v.end());
        a.push_back(v[t]);
        v.erase(v.begin() + t);
    }
    for (auto it = a.begin(); it != a.end(); it++) cout << *it << " "; puts("");
}
int n, q, x, d[21];

signed main(signed argc, char const *argv[]) {
    cin >> n >> q; fac[0] = 1;
    for (ll i = 1; i <= n; i++) fac[i] = fac[i - 1] * i;
    while (q--) {
        char c; cin >> c;
        if (c == 'P') {
            cin >> x;
            decantor(x - 1, n);
        }
        else {
            for (int i = 1; i <= n; i++) cin >> d[i];
            cout << cantor(d, n) + 1 << endl;
        }
    }
}