数学+分类讨论+构造：1102T3

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134191475

http://cplusoj.com/d/senior/p/SS231102C

首先可以通过枚举逆序对点的贡献推出无解情况为 n mod 4>1n \bmod 4 > 1

然后构造可以按 n mod 3n\bmod 3 进行分类

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
#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
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
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 2000010
//#define M
//#define mo
int n, m, i, j, k, T;
int a[N], b[N], mp[N]; 
vector<int>v[N]; 

void lian(int *a, int *b, int x, int y) {
	a[x]=y; b[y]=x; 
}

void fenzhi(int n, int l, int r, int op, int *a, int *b) {
//	debug("%lld [%lld %lld] %lld\n", n, l, r, op); 
	int x, i, j, k, p=l-1; 
	if(!n) return ; 
	if(n==1) return a[l]=b[l]=l, void(); 
	if(op==0) {
		x=(n-1)/3; 		
		if(n<=8) {
//			debug(">> %lld\n", n); 
			if(n!=4 && n!=5 && n!=8) return ; 
			for(i=1; i<=n; ++i) lian(a, b, p+i, p+v[n][i]); 
//			for(i=l; i<=r; ++i) debug("%d ", a[i]); debug("\n"); 
//			for(i=l; i<=r; ++i) debug("%d ", b[i]); debug("\n"); 
			return ; 
		}
		if(n%3==1) {
			for(i=1, j=n; i<=x; ++i, --j) lian(a, b, i+p, j+p); 
			for(i=2, j=n; i<=x+1; ++i, --j) lian(b, a, i+p, j+p); 
			lian(a, b, x+1+p, 1+p); 
			fenzhi(n-2*x-1, l+x+1, r-x, 0, a, b); 
			return ; 
		}
		if(n%3==2) {
			for(i=1, j=n; i<=x; ++i, --j) lian(a, b, i+p, j+p); 
			for(i=2, j=n; i<=x+1; ++i, --j) lian(b, a, i+p, j+p); 
			lian(b, a, 1+p, x+2+p); 
			lian(a, b, x+3+p, r-x); 
			lian(a, b, r-x, x+2+p); 
			fenzhi(n-2*x-3, l+x+2, r-x-1, 1, a, b); 
//			debug("GG "); for(i=l; i<=r; ++i) debug("%d ", a[i]); debug("\n"); 
			return ; 
		}
		if(n%3==0) {
			for(i=1, j=n; i<=x; ++i, --j) lian(a, b, i+p, j+p); 
			for(i=2, j=n; i<=x+1; ++i, --j) lian(b, a, i+p, j+p); 
//			debug("# "); for(i=l+x+1; i<=r-x; ++i) debug("%d ", a[i]); debug("\n"); 
			
			fenzhi(n-2*x-1, l+x+1, r-x, 0, a, b); 
//			debug("# "); for(i=l+x+1; i<=r-x; ++i) debug("%d ", a[i]); debug("\n"); 
//			for(i=l+x+1; i<=r-x; ++i) debug("%d ", abs(a[i]-i)); debug("\n"); 
			
			lian(a, b, x+1+p, r-x); lian(a, b, x+2+p, l); 
//			for(i=l; i<=r; ++i) debug("%d ", abs(a[i]-i)); debug("\n"); 
			return ; 
		}
	}
	if(op==1) {
		x=n/3-1; 
		for(i=1, j=n; i<=x; ++i, --j) lian(b, a, i+p, j+p); 
		for(i=2, j=n; i<=x+1; ++i, --j) lian(a, b, i+p, j+p); 
		lian(a, b, l-2, x+1+p); 
		if(n<=5) {
			if(n==4) {
				lian(a, b, l-2, l+1); 
				lian(a, b, l+1, l+2); 
				lian(a, b, l+2, l); 
				lian(a, b, r, r); 
			}
			if(n==5) {
				lian(a, b, l-2, l+1); 
				lian(a, b, l+1, l+2); 
				lian(a, b, l+2, r); 
				lian(a, b, l+3, l+3); 
				lian(a, b, r, l); 
			}
			return ; 
		}
		if(n%3==0) {
			fenzhi(n-2*x-1, l+x+1, r-x, 0, a, b); 
			return ; 
		}
		if(n%3==1) {
		lian(a, b, l-2, x+2+p); 
			lian(a, b, x+2+p, r-x); 
			lian(a, b, r-x, x+3+p); 
			fenzhi(n-2*x-3, l+x+2, r-x-1, 1, b, a); 
			return ; 
		}
		if(n%3==2) {
			fenzhi(n-2*x-1, l+x+1, r-x, 0, b, a); 
			lian(a, b, l-2, x+2+p); 
			lian(a, b, r-x, x+1+p); 
			return ; 
		}
	}
}

signed main()
{
	freopen("destruction.in", "r", stdin);
	freopen("destruction.out", "w", stdout);
	#ifdef LOCAL
		freopen("in.txt", "r", stdin);
		freopen("out.txt", "w", stdout);
	#endif
	v[4]={0, 4, 2, 1, 3}; 
	v[5]={0, 5, 3, 1, 4, 2}; 
	v[8]={0, 8, 7, 5, 4, 1, 3, 6, 2}; 
	T=read();
	while(T--) {
		n=m=read(); 
		if(n%4 && (n-1)%4) { printf("-1\n"); continue; }
		for(i=1; i<=n; ++i) a[i]=b[i]=i; 
		fenzhi(n, 1, n, 0, a, b); 
//		memset(mp, 0, sizeof(mp));
		 
		for(i=1; i<=n; ++i) printf("%d ", a[i]);
//		debug("\n"); 
//		for(i=1; i<=n; ++i) debug("%2d ", i);
//		debug("\n") ; 
//		for(i=1; i<=n; ++i) debug("%d ", abs(a[i]-i)); 
//		for(i=1; i<=n; ++i) if(mp[abs(a[i]-i)]) break; else mp[abs(a[i]-i)]=1; 
//		if(i<=n) printf("\nsdfasfsad asdf safasdf %lld\n", n); 
		printf("\n"); 
	}
	
	return 0;
}