洛谷 P5461 赦免战俘

// 洛谷 P5461 赦免战俘 —— 第 ① 版：递归的时候顺手就把答案打出来（**这一版是错的**）
//
// 输入：n（n <= 10）
// 输出：本该是 2^n × 2^n 的 01 矩阵
//
// 这份为什么存在：分治的思路完全对 —— 切成四块，左上角整块赦免，另外三块继续切。
// 而人写到这一步，最顺手的动作就是「算到哪儿就打到哪儿」。
//
// ⚠ 但它错得很彻底，而且错在一个和算法无关的地方：**递归是按「块」走的，输出是按「行」走的。**
//    递归先把左上那一整块处理完，才轮到右上 —— 可这两块在同一批行里。
//    于是打出来的东西，每一行都是从别的块拼过来的碎片，**根本对不上位置**。
//
// ★ 这是初学分治最常见的一种翻车，值得单独记住一句话：
//   **递归的顺序 ≠ 输出的顺序。** 只要两者不一致，就必须先把结果存下来，最后统一输出。

#include <bits/stdc++.h>
using namespace std;

// 处理左上角在 (r, c)、边长为 len 的正方形
void solve(int r, int c, int len) {
    if (len == 1) { cout << 1 << " "; return; }        // 分不下去了，这一个不赦免

    int h = len / 2;
    for (int i = 0; i < h; i++)                        // 左上角整块赦免
        for (int j = 0; j < h; j++) cout << 0 << " ";

    solve(r, c + h, h);                                // 右上
    solve(r + h, c, h);                                // 左下
    solve(r + h, c + h, h);                            // 右下
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    solve(0, 0, 1 << n);
    cout << "\n";
    return 0;
}

// 洛谷 P5461 赦免战俘 —— 第 ② 版：先填进数组，最后统一输出（答案对了）
//
// 输入：n
// 输出：2^n × 2^n 的 01 矩阵
//
// 这份为什么存在：第 ① 版的病根是「递归按块走、输出按行走」。
// 治法只有一个：**先把结果填进一个二维数组，等递归全部结束，再一行一行打出来。**
// 递归函数从此不负责输出，只负责「往格子里写数」。
//
// ★ 答案这下全对了。但这一版还有一个和算法完全无关的问题，第 ③ 版收拾它：
//   n = 10 时要打出 1024 × 1024 = 1 048 576 个数。
//   这一版用的是没关同步的 cout，还每行 endl 刷一次缓冲 —— 光是输出就可能把时限吃光。
//   ⇒ **「算得快」和「打得快」是两件事**，这道题两件都要管。

#include <bits/stdc++.h>
using namespace std;

int a[1030][1030];

void solve(int r, int c, int len) {
    if (len == 1) { a[r][c] = 1; return; }             // 分不下去了，这一个不赦免

    int h = len / 2;
    for (int i = r; i < r + h; i++)                    // 左上角整块赦免（填 0，本来就是 0）
        for (int j = c; j < c + h; j++) a[i][j] = 0;

    solve(r, c + h, h);
    solve(r + h, c, h);
    solve(r + h, c + h, h);
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    int m = 1 << n;
    solve(0, 0, m);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) cout << a[i][j] << (j + 1 < m ? " " : "");
        cout << endl;                                  // ⚠ 每行刷一次缓冲，1024 行就是 1024 次
    }
    return 0;
}

// 洛谷 P5461 赦免战俘 —— 第 ③ 版：把输出也弄快（正解）
//
// 输入：n（n <= 10）
// 输出：2^n × 2^n 的 01 矩阵，数字之间一个空格
//
// 和第 ② 版的差别**只有输出那几行**，算法一个字没改：
//   · ios::sync_with_stdio(false) —— 断开 cout 和 C 的 stdio 同步（这份代码不用 printf，所以安全）
//   · endl 换成 '\n' —— endl 会**强制刷缓冲**，1024 行就是 1024 次系统调用
//
// ⚠ 这两条只在「输出量很大」的题里才要紧，而这道题正是：
//   n = 10 时要打 1 048 576 个数。平时的题目输出几行，加不加毫无区别，别当成万能咒语。
//
// ⚠⚠ 关同步有个**必须记住的前提**：这份代码里不能再出现 printf。
//    cout 和 printf 各自缓冲，混用又关了同步，打印顺序会乱掉（这本书在第 26 章踩过）。

#include <bits/stdc++.h>
using namespace std;

int a[1030][1030];

// 处理左上角在 (r, c)、边长为 len 的正方形：左上那一小块整块赦免，另外三块继续分
void solve(int r, int c, int len) {
    if (len == 1) { a[r][c] = 1; return; }

    int h = len / 2;
    solve(r, c + h, h);                                // 右上
    solve(r + h, c, h);                                // 左下
    solve(r + h, c + h, h);                            // 右下
    // 左上那一块什么都不用做 —— 数组本来就是 0，而 0 正是「被赦免」
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    int m = 1 << n;
    solve(0, 0, m);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) cout << a[i][j] << (j + 1 < m ? " " : "");
        cout << '\n';
    }
    return 0;
}

// 洛谷 P5461 赦免战俘 —— 第 ④ 版：写完之后回头看，它其实有个闭式（不用递归）
//
// 输入：n
// 输出：和第 ③ 版逐字节相同
//
// 这份为什么存在：**递归写对了不是终点**。把它写对之后回头盯着那张图看，
// 常常能看出一条一句话就能说清的规律 —— 而看出来的过程本身就是收获。
//
// 推导（跟着走一遍，三十秒）：
//   一个人最终是 1（不被赦免），当且仅当**他每一层都没落进左上角那一块**。
//   而「落进左上块」= 这一层里，行号和列号的那一个二进制位**同时是 0**。
//   ⇒ 他是 1 ⟺ 行号和列号的**每一个二进制位都不同时为 0**
//   ⇒ 也就是 (i | j) 的每一位都是 1
//   ⇒ i | j == 2^n - 1
//
// 拿 n = 3 验一下（下标从 0 数）：
//   最后一行 i = 7 = 111，那么 i | j == 7 恒成立 ⇒ 整行全是 1 ✓（对照样例）
//   第一行 i = 0，要 i | j == 7 只能 j = 7 ⇒ 只有最右边是 1 ✓
//
// ★ 这一版不是「更优解」—— 第 ③ 版早就够快了。它的价值在于：
//   **一个分治过程，常常等价于一句关于二进制位的话。**
//   第 28 章状压、第 38 章树状数组都会再见到这种「下标的二进制形状」。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    int m = 1 << n, full = m - 1;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++)
            cout << ((i | j) == full ? 1 : 0) << (j + 1 < m ? " " : "");
        cout << '\n';
    }
    return 0;
}