「MX-X5 / GFOI Round 1」T7 Der Richter 题解

· · 题解

首先考虑怎么对一个极好的排列 p 求 f(p)。

枚举一个正整数 x，把排列中 \le x 的数设成 0，> x 的数设成 1。

那么交换这个排列使得 \max\limits_{i = 1}^x p_i = x 的最小操作次数就是这个 01 串的逆序对数。

交换这个排列使其变成好的的最小操作次数就是对于所有可能的 x 对应的 01 串的逆序对数的最小值。

因为 p 是极好的，所以最小值对应的那个 01 串一定是唯一的。称这个 01 串是排列 p 的关键串。

把这个 01 串拿出来，那么 f(p) 就是这个 01 串，一次可以交换相邻的一对 10，交换使得其有序的交换方案个数。

考虑把 0 看成向右走，1 看成向上走，这样可以画出来一个杨表的轮廓。然后交换相邻的一对 10 等价于删掉杨表中处于其所在行第一个和其所在列第一个的格子。可以发现方案数就是这个杨表的勾长公式。

因为 n \le 80 所以杨表格子数 \le 79。可以先考虑直接搜正整数拆分得到杨表，然后再把它的轮廓转成一个 1 开头 0 结尾的 01 串。

现在我们的问题是要在其开头添加最少个数的 0，结尾添加最少个数的 1，使得存在一种将这个 01 串转成排列的方案，且这个 01 串是这个排列的关键串。要求最少个数的原因是，回答询问时要枚举一个 n' \le n，使得存在长度为 n' 的 01 串且交换方案数为 m，找到这个 01 串之后可以在前面补 n - n' 个 0 或在后面补 n - n' 个 1，再将其转成排列。

结论：设这个 01 串逆序对数（即搜出来的杨表格子数）为 k，01 串长度为 l，那么要在开头添加 k - l + 2 个 0，在结尾添加 k - l + 2 个 1。将一个 01 串转化成排列的方法是，设 1 的个数为 t，从左往右将 1 填成 n, n - 1, \ldots, n - t + 1，再从左往右将 0 填成 n - t, n - t - 1, \ldots, 1。

注意到只有 2k - l + 4 \le 80 的杨表才有用（称其为有效状态），所以边搜边剪枝，可以保证不会搜到无效状态。

可以使用哈希表存储所有形如 (\text{长度}, \text{交换方案数}, \text{01 串}) 的三元组。

时间复杂度 O((a(n) + q)n)，其中 a(n) 为有效状态数，当 n = 80 时 a(n) \approx 2 \times 10^6。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef __int128 lll;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;

const int maxn = 85;
const int P = 5000011;

ll n, m, mod, a[maxn], fac[maxn], inv[maxn], b[maxn];
__gnu_pbds::gp_hash_table<ll, lll> mp[maxn];

void dfs(int s, int lst, ll res, lll x) {
    if (s) {
        ll re = res * fac[s] % mod;
        int t = s - (m + lst) + 2;
        mp[m + lst + t * 2][re] = (x << t) | ((((lll)1) << t) - 1);
    }
    for (int i = lst; s + i <= 79; ++i) {
        if (2 * (s + i) - (m + 1 + i) + 4 > 80) {
            continue;
        }
        a[++m] = i;
        ll r = res;
        for (int j = 1; j <= i; ++j) {
            r = r * inv[i - j + (++b[j])] % mod;
        }
        dfs(s + i, i, r, ((x << (a[m] - a[m - 1])) | ((((lll)1) << (a[m] - a[m - 1])) - 1)) << 1);
        for (int j = 1; j <= i; ++j) {
            --b[j];
        }
        --m;
    }
}

inline void init() {
    fac[0] = 1;
    for (int i = 1; i <= 80; ++i) {
        fac[i] = fac[i - 1] * i % mod;
    }
    inv[1] = 1;
    for (int i = 2; i <= 80; ++i) {
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    }
    dfs(0, 1, 1, 0);
}

void solve() {
    scanf("%lld%lld", &n, &m);
    if (m == 1) {
        for (int i = 1; i <= n; ++i) {
            printf("%d%c", i, " \n"[i == n]);
        }
        return;
    }
    for (int i = n; i >= 2; --i) {
        if (mp[i].find(m) != mp[i].end()) {
            lll x = mp[i][m];
            ll t = n;
            for (int j = 1; j <= n; ++j) {
                if ((x >> (n - j)) & 1) {
                    a[j] = (t--);
                }
            }
            for (int j = 1; j <= n; ++j) {
                if (((~x) >> (n - j)) & 1) {
                    a[j] = (t--);
                }
            }
            for (int j = 1; j <= n; ++j) {
                printf("%lld%c", a[j], " \n"[j == n]);
            }
            return;
        }
    }
    puts("-1");
}

int main() {
    int T = 1;
    scanf("%d%lld", &T, &mod);
    init();
    while (T--) {
        solve();
    }
    return 0;
}