分治递归： 用递归的方式实现分治策略

分治： 把一个大问题分解成若干个相似的子问题 分别解决后再合并结果

递归： 函数调用自身

#r是行 c是列 size是边长 grid是方形列表
#正方形会一直递归到被分割成一个单独的像素后才会停止
def fill_grid(r, c, size, grid):
    if size == 1:
        grid[r][c] = 1
        return
    half = size // 2
    #左上
    fill_grid(r,c,half,grid)
    #右下
    fill_grid(r+half,c+half,half,grid)
    #左下
    fill_grid(r+half,c,half,grid)

def main():
    n = int(input().strip())
    size = 2 ** n
    grid = [[0] * size for _ in range(size)]
    #先从左上角开始 是因为左上角可以只通过加法 到达左下 右下 
    fill_grid(0,0,size,grid)

    for i in range(size):
        #按行打印
        print(' '.join(map(str,grid[i])))
if __name__ == "__main__":
    main()