ICPC2026网络赛1 E. LCM Permutation

LCM Permutation - Problem - QOJ.ac

image-20260908204953730

我不知道怎么形容这题好，反正很神。此处只描述做法，因为我也不知道怎么std是怎么想出来的。

首先，对于 n≤13n\le 13 这个级别的，我们直接 O(n!)O(n!) 即可（因为必然有解，所以其实是 O((n−1)!)O((n-1)!)）

接下来，我们对 14≤n≤2514\le n\le 25，我们尝试令这个LCM L=168=23×3×7L=168=2^3\times 3\times 7 。接下来我们尝试构造一个合法排列。

如果两个数 ai+aj∣La_i+a_j|L，我们就在 ii 和 jj 之间连边。那样子我们本质上要求一个哈密顿回路。这是一个NP-hard问题，我们直接暴力求解，注意可以贪心跑当前可到且剩余度数最小的点。

为了后续操作方便，我们可以令开始点为1，结束点为2，现在变成跑哈密顿路径了。

对于 26≤n≤2726\le n\le 27，我们可以令 L=336=168×2L=336=168\times 2，做法同上。我们令我们构造出来满足题意的排列叫做排列 PP。在上面的情况里，L∼12nL\sim12n

接下来，我们考虑 n≥28n\ge 28 的情况。

我们考虑分治的思想，我们可以把两个子排列合并成我们最终的排列。原先两个子排列满足 x+y∣Lx+y|L，我们试图让这个新排列满足 x+y∣2Lx+y|2L。那样子我们始终就满足 L∼12nL\sim 12n。

一个常见的考虑角度就是奇偶构造。直接上手似乎不方便，所以我们需要一个辅助排列 QQ，满足 x+y−1∣Lx+y-1|L。

注意，无论我们构造的 PP 或 QQ，始终满足以1开头，以2结尾。

现在我们用这种方式构造排列 PP：

  • 对于前 ⌈n2⌉\lceil \dfrac n 2\rceil 个数，我们构造子排列 QQ。随后令 x=2x−1x=2x-1。因此相邻两项 (2x−1)+(2y−1)=2(x+y−1)(2x-1)+(2y-1)=2(x+y-1)，又 x+y−1∣Lx+y-1|L，所以 2L∣(2x−1)+(2y−1)2L|(2x-1)+(2y-1) 成立
  • 对于后 ⌊n2⌋\lfloor \dfrac n 2\rfloor 个数，我们构造子排列 PP。随后先翻转，再令 x=2xx=2x，此时 2x+2y=2(x+y)≡0(mod2L)2x+2y=2(x+y)\equiv 0\pmod {2L} 成立。

对于交界处：我们从 1 ... 2 2 .. 1 得到 1 ... 3 4 ... 2 ，其中 1+2 和 3+4 都是168的因数，而扩展出的新排列仍然是以1开头，以2结尾。

因此，通过上述构造，我们既满足了每一个数都出现一次，又让其LCM变成了 2L2L。成立！

构造 QQ 的方式同理，此处只给出构造方式，证明同理：

  • n≡0(mod2)n\equiv 0\pmod 2

    • 先构造一个长为 n2\dfrac n 2 的子排列 QQ，然后令 x=2x−(i&1)x=2x-(i\&1)，其中 ii 为最终位置的编号
    • 再构造一个长为 n2\dfrac n 2 的子排列 QQ，然后先翻转，再令 x=2x−(i&1)x=2x-(i\&1)，其中 ii 为最终位置的编号

  • n≡1(mod2)n\equiv 1\pmod 2

    • 先在最开始放一个1

    • 先构造一个长为 n2\dfrac n 2 的子排列 PP，然后令 x=2x+(i&1)x=2x+(i\&1)，其中 ii 为最终位置的编号

    • 再构造一个长为 n2\dfrac n 2 的子排列 PP，然后先翻转，再令 x=2x+(i&1)x=2x+(i\&1)，其中 ii 为最终位置的编号

我们证明时只需要验证一下内容即可：

  1. 每个数只恰好出现1次（满足排列性质）
  2. 满足 x+y∣2Lx+y|2L（或 x+y−1∣2Lx+y-1|2L）
  3. 开头为1，结尾为2

只能说真的是很神仙的题目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
//#define int long long
int ptr = 0; char buf[1 << 23];
inline void writeChar(char c) {
	if (ptr == 1 << 23) fwrite(buf, 1, ptr, stdout), ptr = 0; 
	buf[ptr++] = c;
}
inline void writeInt(int x) {
	int t = 0; char s[10];
	while (x) s[t++] = (char)('0' + x % 10), x /= 10;
	while (t) writeChar(s[--t]);
}
inline void flushOut() {
	if (ptr) fwrite(buf, 1, ptr, stdout), ptr = 0;
}
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 35
vector<int> solveP(int n); 
vector<int> solveQ(int n); 
int n, m, i, j, k, T;
vector<int>P[N], Q[N]; 
int G[N], path[N]; 

vector<int> Hami(int n, int os, int L) {
	int i, j; 
	for(i = 0; i < n; ++i) G[i] = 0; 
	for(i = 0; i < n; ++i)
		for(j = i + 1; j < n; ++j) 
			if(L % (i + j + 2 - os) == 0) {
				G[i] |= (1 << j); 
				G[j] |= (1 << i); 
//				debug("Cun(%d %d)\n", i, j); 
			}
	vector<int>ans; path[0] = 0; 
//	debug("--------\n"); 
	function<bool(int, int)> dfs = [&](int u, int mask) -> bool {
//		debug("%d %d\n", u, mask); 
		if(mask == (1 << n) - 1) {
//			debug("step 1\n"); 
			if(u == 1) {
//				debug("step 2!\n"); 
				for(i = 0; i < n; ++i) ans.pb(path[i] + 1); 
				return true; 
			}
			return false; 
		}
		int avail = G[u] & ~mask; 
		vector<pair<int, int> > cand; 
		for(int v = 0; v < n; ++v) 
			if((avail >> v) & 1) {
				int cnt = __builtin_popcount(G[v] & ~mask); 
				cand.pb({cnt, v}); 
			}
		sort(cand.begin(), cand.end()); 
		for(auto t : cand) {
			path[__builtin_popcount(mask)] = t.se; 
			if(dfs(t.se, mask | (1 << t.se))) return true; 
		}
		return false; 
	}; 
	bool x = dfs(0, 1); 
//	printf("For %d %d\n", n, os); 
//	cout << x << endl; 
	return ans; 
}

void init() {
	int p[N]; 
	for(n = 1; n <= 13; ++n) {
		for(i = 1; i <= n; ++i) p[i] = i; 
		do {
			int L = 1; 
			for(i = 1; i <= n; ++i) {
				int x = p[i] + p[i % n + 1]; 
				L = L / __gcd(L, x) * x; 
				if(L > 20 * n) break; 
			}
			if(i > n) break; 
		}while(next_permutation(p + 1, p + n + 1)); 
		for(i = 1; i <= n; ++i) P[n].pb(p[i]); 
//		for(auto t : P[n]) debug("%d ", t); debug("\n"); 
	}
	for(n = 14; n <= 27; ++n) {
		int lmit = (n <= 25 ? 168 : 336); 
		P[n] = Hami(n, 0, lmit); 
		Q[n] = Hami(n, 1, lmit); 
	}
}

vector<int> solveP(int n) {
	debug("Construct P %d\n", n); //system("pause"); 
	if(n <= 27) return P[n]; 
	int n1 = (n + 1) / 2, n2 = n / 2; 
	auto a1 = solveQ(n1); 
	auto a2 = solveP(n2); 
	vector<int>ans; 
	reverse(a2.begin(), a2.end()); 
	for(auto t : a1) ans.pb(t * 2 - 1); 
	for(auto t : a2) ans.pb(t * 2); 
	return ans; 
}

vector<int> solveQ(int n) {
	debug("Construct Q %d\n", n); 
	if(n <= 27) return Q[n]; 
	vector<int>ans; 
	if(n % 2 == 0) {
		auto a = solveQ(n / 2); 
		int i = 0; 
		for(auto t : a) ++i, ans.pb(2 * t - i % 2); 
		reverse(a.begin(), a.end()); 
		for(auto t : a) ++i, ans.pb(2 * t - i % 2); 
		return ans; 
	}
	else {
		ans.pb(1); 
		auto a = solveP(n / 2);  
		int i = 0; 
		for(auto t : a) ++i, ans.pb(2 * t + i % 2); 
		reverse(a.begin(), a.end()); 
		for(auto t : a) ++i, ans.pb(2 * t + i % 2); 
		return ans; 
	}
	
}

signed main() {
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T = read();
//	while(T--) {
//
//	}
	init(); 
	T = read(); 
	while(T--) {
		n = read(); 
		if(n < 28) {
			for(i = 0; i < n; ++i) writeInt(P[n][i]), writeChar(' '); 
		}
		else {
			auto ans = solveP(n); 
			for(auto t : ans) writeInt(t), writeChar(' '); 
		}
		writeChar('\n'); //flushOut();
	}
	flushOut();
	return 0;
}