洛谷P5461的几种解法
Andreo Y.隔离在浦东的第二天，精神振奋且萎靡 ，百无聊赖，于是又登上洛谷开始新一次的C++康复训练。
题目本身比较简单，能够AC算法也容易想。但是正因为简单，这道题的解法拥有更强的开放性，研究起来也更加上头。
原题链接：P5461 赦免战俘 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
原题呈现 赦免战俘（洛谷月赛）
题目背景
借助反作弊系统，一些在月赛有抄袭作弊行为的选手被抓出来了！
题目描述
现有 $2^n\times 2^n (n\le10)$ 名作弊者站成一个正方形方阵等候 kkksc03 的发落。kkksc03 决定赦免一些作弊者。他将正方形矩阵均分为 4 个更小的正方形矩阵，每个更小的矩阵的边长是原矩阵的一半。其中左上角那一个矩阵的所有作弊者都将得到赦免，剩下 3 个小矩阵中，每一个矩阵继续分为 4 个更小的矩阵，然后通过同样的方式赦免作弊者……直到矩阵无法再分下去为止。所有没有被赦免的作弊者都将被处以棕名处罚。
给出 $n$，请输出每名作弊者的命运，其中 0 代表被赦免，1 代表不被赦免。
输入格式
一个整数 $n$。
输出格式
$2^n \times 2^n$ 的 01 矩阵，代表每个人是否被赦免。数字之间有一个空格。
样例 #1
样例输入 #1
3
样例输出 #1
0 0 0 0 0 0 0 1
0 0 0 0 0 0 1 1
0 0 0 0 0 1 0 1
0 0 0 0 1 1 1 1
0 0 0 1 0 0 0 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
题解
函数递归模拟
常规解法，一遍AC。开O2之后时间也比较充裕。
很容易想到的方法就是直接从原正方形开始，每次分成四个区域，把第一个区域的值赋为0，然后依次递归另外三个区域，直到递归到的正方形边长为1为止。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
bool remit[2000][2000];
void divide(int a,int x0,int y0)
{
if(a==1) return; //当不能再分的时候回退到上一层
a>>=1;
for(int i=x0;i<x0+a;i++)
for(int j=y0;j<y0+a;j++)
remit[i][j]=0;
//继续分下一层，递归
divide(a,x0+a,y0);
divide(a,x0,y0+a);
divide(a,x0+a,y0+a);
return;
}
void output() //繁琐的输出，不想写进主函数
{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cout<<remit[i][j];
if(j<n-1) cout<<' ';
}
cout<<endl;
}
}
int main()
{
cin>>n;
n=1<<n;
memset(remit,1,sizeof(remit)); //初始化整个数组为1
divide(n,0,0);
output();
return 0;
}
数论（找规律）
从时间消耗和空间占用来看，这个算法应该是三个算法中最佳的。由于只和i和j的值有关，内存占用来到了惊人的371B。
注意到，这个输出的正方形一定是对称的。对称性是通向数学巧解的钥匙。我们标出每个战俘对应的行号和列号，再来观察一下这个输出：
| remit[][] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 3 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 4 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 5 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 6 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
似乎还是不太明显
由于这个题目条件和2的乘方有很大关联，我们不妨试试吧行列号写成二进制：
| remit[][] | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
| 000 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| 001 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 010 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
| 011 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 100 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 101 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 110 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| 111 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
既然是二进制了，那就躲不开位运算。适当观察，可以发现，remit[i][j]的值由i和j决定。当i|j==111，也就是i|j==2^n-1，那么remit[i][j]=1，否则为0。
这个通过找规律观察出来的结论用数论证明也不难。读者自证 还是写一下，权当练习证明逻辑性罢
数学说明
欲证，即证$i|j$有任何一位为0时，remit[i][j]即为0。
所以，只需对每一个k都判断一遍该位是否i和j都为零即可。
反过来，当没有0时，就有$i|j=2^n-1$，根据这个式子判断，不需要循环，更加优美。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
int main()
{
cin>>n;
n=1<<n; //预先处理n的值，简化后续代码 因此注意后续代码中n就是原来的2^n-1
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
bool tmp=(i|j)!=(n-1)?0:1; //用一下单行if XD 看着更简洁点
if(j<n-1) cout<<tmp<<' '; //听说洛谷现在已经不查行末空格的问题了，不知道是不是真的
else cout<<tmp;
}
cout<<endl;
}
return 0;
}
类杨辉三角（转自这篇题解）
时间复杂度和法二几乎一样，但是相比法二空间占用更大，需要开数组。
其实和法二的核心是一样的，只是用一个更常见的模型套了一下，可能会更好理解和运用。
每一个数字都是它上方数字加上右上方数字再模2。
其实就是不进位加法，异或一下就好了。
代码（经过微调）
#include<bits/stdc++.h>
#define re register
using namespace std;
int n;
int a[1234][1234];
int main()
{
scanf("%d",&n);
n = (1<<n);
a[0][n+1] = 1;
for(re int i=1;i<=n;++i)
{
for(re int j=1;j<=n;++j)
{
a[i][j] = a[i-1][j] ^ a[i-1][j+1];
printf("%d ",a[i][j]);
}
printf("\n");
}
return 0;
}