C. Magic Grid(构造题，异或性质)

今天写的主要是概率题，但是三道还不足作为归纳，明天一起发。
这个构造题提供两个思路

C. Magic Grid

题意：给定一个正整数n是4的倍数，请你构造一个nn的矩阵，矩阵内元素满足从0到nn-1出现一次且仅一次。

1.异或性质。

对于连续的数，我们知道连续的两个数互质，但是还有一个性质，就是连续的四个数异或和为0，然后像0 4 8 12这样相隔4个的数异或和也是0

所以我们可以按照这种顺序来构造。

4
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

1
2
3
4
5
6

然后

8
0 1 2 3 32 33 34 35
4 5 6 7 36 37 38 39
8 9 10 11 40 41 42 43
12 13 14 15 44 45 46 47
16 17 18 19 48 49 50 51
20 21 22 23 52 53 54 55
24 25 26 27 56 57 58 59
28 29 30 31 60 61 62 63
1
2
3
4
5
6
7
8
9

#include
using namespace std;

const int N=2010;
int t,n,m;
int a[N][N];

signed main()
{
	cin>>n;
	int x=n/4;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			a[i][j]=4*(i-1)+j-1+((j-1)/4)*16*x-(j-1)/4*4;
			cout<<a[i][j]<<" ";
		}
		cout<<'\n';
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.打表后观察。

这种思路其实，，确实很难，而且你最后观察出来的东西实际上和上面说的性质是大同小异的。

观察
发现貌似只要将相邻两列的前n/2行和后n/2交换就可以了，

4
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
1
2
3
4
5

8
0 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
1
2
3
4
5
6
7
8
9

12
0 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
1
2
3
4
5
6
7
8
9
10
11
12
13

所以就又有了这样的呆码

#include
using namespace std;
int n,tot;
int a[1010][1010];
int main() {
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
	    for(int j=1; j<=n; j++)
	        a[i][j]=tot++;		
	}
	for(int i=1; i<=n/2; i++) {
		for(int j=1; j<=n; j+=2) 
			cout<<a[i][j]<<" "<<a[i+n/2][j]<<" ";
		cout<<endl;
	}
	for(int i=1; i<=n/2; i++) {
		for(int j=2; j<=n; j+=2)
		    cout<<a[i][j]<<" "<<a[i+n/2][j]<<" ";
		cout<<endl; 
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22