自动搬运

查看原文

来自洛谷，原作者为

	EuphoricStar Remember.

搬运于2025-08-24 23:04:33，当前版本为作者最后更新于2024-09-29 15:36:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先考虑怎么对一个极好的排列 $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;
}