自动搬运

查看原文

来自洛谷，原作者为

	zyh_helen 是一本除小说主角外所有人都是小说主角的小说的主角

搬运于2025-08-24 23:05:26，当前版本为作者最后更新于2024-10-31 16:21:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不算太难但很有意思的一道题，这里提供一下我的构造方法。

考虑限制给到了 $m\le n+1$，我们直接取满。

我们确定两个状态使其一部分情况最终到这个值，另一部分状态最终到另一个值，这两个值封闭；为了最小化影响，我们直接使这两个值分别为 $n$ 和 $m$（即第 $n$ 行都是 $n$，第 $m$ 行都是 $m$）。

我们手模一下小数据找找灵感，$k=0$ 的时候我们显然直接让 $n$ 这个值无法到达就行了；但 $k=1$ 就不那么好办了，我们要构造出来一条路径经过所有值一次，相当于确定出一个排列，大概就是这样（拿 $n=8$ 举个例子）：

2 9 9 9 9 9 9 8 9
9 3 9 9 9 9 9 8 9
9 9 4 9 9 9 9 8 9
9 9 9 5 9 9 9 8 9
9 9 9 9 6 9 9 8 9
9 9 9 9 9 7 9 8 9
9 9 9 9 9 9 8 8 9
9 9 9 9 9 9 9 8 9

显然只能沿着不是 $m$ 的数一路走到 $n$。

我们沿着 $k=1$ 继续想，如果第 $i$ 列的某个值给到了 $n$，那么相当于走到该值后的 $n-i$ 个操作随意排列，即给答案增加了 $(n-i)!$，同时注意到第 $i$ 列还剩下 $n-i+1$ 个值都可以自由改动（其他的值在此之前都被调用过了），也就是在第 $i$ 行 $k\in[0,(n-i+1)!]$ 都可以被处理（如果用 $(n-i)!$ 处理完还有剩余就像 $k=1$ 一样引导其走到下一列再处理）。

易证 $\forall k \in [0,n!]$ 可以处理。

代码实现不难，注意特判 $n=1,k=0$ 的情况。

#include<bits/stdc++.h>
//#include<Windows.h>
#define int long long
//#define ll long long
#define double long double
#define fi first
#define se second
//#define ls t[p].l
//#define rs t[p].r
#define y1 yyyyyyyyyyyyyyyy1
using namespace std;
const int N = 3e5 + 10, inf = 1e12, M = 101;
const double eps = 1e-14, pi = 3.1415926, kou = 0.577215669902;
const int mod = 1e9 + 7;
//const int AQX = 9;
mt19937 rnd(time(0) ^ clock());
int random(int l, int r){
	return rnd() % (r - l + 1) + l;
}
/*
		    	           _      _        _          
			       ____  _| |_   | |_  ___| |___ _ _  
			      |_ / || | ' \  | ' \/ -_) / -_) ' \ 
			      /__|\_, |_||_|_|_||_\___|_\___|_||_|
			          |__/    |___|                              
				       
*/
//struct Graph{
//	int head[N], tot = 1;
//	struct edge{
//		int t;
//		int d, fa, f;
//		int next;
//	}e[N << 1];
//	void edge_add(int u, int v, int w = 0){
//		e[++tot].next = head[u];
//		e[tot].t = v;
//		e[tot].d = w;
//		e[tot].f = u;
//		head[u] = tot;
//	}
//	void clear(int n){
//		for(int i = 1;i <= tot;i++)e[i].t = e[i].f = e[i].d = e[i].next = 0;
//		for(int i = 1;i <= n;i++)head[i] = 0;
//		tot = 0;
//	}
//}g;
//int qmr(int x, int a){
//	int ret = 1, p = x;
//	while(a){
//		if(a & 1)ret = ret * p % mod;
//		p = p * p % mod;
//		a >>= 1;
//	}
//	return ret;
//}


int n, k, jc[N], ans[20][20];
signed main(){
	int T, lsj;
	cin >> lsj >> T;
	jc[0] = 1;
	for(int i = 1;i <= 12;i++)jc[i] = jc[i - 1] * i % mod;
	while(T--){
		cin >> n >> k;
		if(n == 1 && k == 0){
			cout << 2 << " " << 2 << endl;
			printf("1 1\n");
			continue;
		}
		cout << n + 1 << " " << n << endl;
		for(int i = 1;i < n;i++){
			int p = jc[n - i], j = n;
			for(;k >= p;k -= p, j--)ans[i][j] = n;
			for(;j;j--)ans[i][j] = n + 1;
			if(k)ans[i][i] = i + 1;
		}
		for(int i = 1;i <= n;i++){
			for(int j = 1;j < n;j++)printf("%lld ", ans[j][i]);
			printf("%lld %lld\n", n, n + 1);
		}
	}
	return 0;
}