【思维】P5461 赦免战俘——两种有趣思路，分析推导

P5461 赦免战俘 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解 P5461 【赦免战俘】 - Flandre_495 的博客 - 洛谷博客 (luogu.com.cn)

题解 P5461 【赦免战俘】 - Ritanlisa 的博客 - 洛谷博客 (luogu.org)

通用解法是分治/模拟+递归，但这两种解法直接推出公式，很有意思。

题解1的主要思路：

每一个数字都是它上方数字加上右上方数字再模2。其实就是不进位加法，异或一下就好了。

 a[i][j] = a[i-1][j] ^ a[i-1][j+1]; 

 根据题解2所写的代码：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
using namespace std;
int n,m;
int main(){    
    cin>>n;
    m=(1<<n);
    rep(i,0,m){
        rep(j,0,m){
            cout<<((i|j)==((1<<n)-1)?1:0)<<' ';
        }             
        cout<<endl;
    }        
    return 0;
}