題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟠 ABC436B Magic Square

Problem Statement

題意簡述

給定一個 $N \times N$ 的網格（ $N$ 為大於等於 3 的奇數），初始全空。
按照以下規則填入 $1$ 到 $N^2$ 的整數：

在 $(0, \frac{N-1}{2})$ 填入 $1$ 。
重複 $N^2-1$ 次：
設上一個填入的數字 $k$ 位於 $(r, c)$ 。
若右上方的格子 $((r-1) \bmod N, (c+1) \bmod N)$ 為空，則在該處填入 $k+1$ 。
否則（該格已被佔用），在正下方的格子 $((r+1) \bmod N, c)$ 填入 $k+1$ 。

求最終網格的狀態。題目保證每個格子恰好被填入一次。

Constraints

約束條件

$3 \le N \le 99$
$N$ 是奇數

思路：Siamese Method (De la Loubère method)

這道題目描述的正是構造 奇數階魔方陣 (Magic Square) 的經典演算法 —— Siamese Method。

為什麼保證有解？

題目要求證明依照此規則操作，每個格子會恰好被填入一次。我們可以將其分解為向量移動與模運算的性質來理解。

基本移動與週期性
主要的移動向量是 $v_1 = (-1, 1)$ （即右上方）。
在模 $N$ 的二維環面上，位置 $P_k = P_0 + k \cdot v_1 \pmod N$ 。
由於 $N$ 是奇數， $\gcd(N, -1) = \gcd(N, 1) = 1$ ，這意味著如果沒有阻擋， $v_1$ 方向的路徑會形成一個長度為 $N$ 的循環 (Cycle)，恰好遍歷 $N$ 個不同的格子後回到起點。
衝突發生的時機
因為上述的循環特性，當我們連續填入 $N$ 個數字後（例如 $1$ 到 $N$ ），下一個位置（原本是 $N+1$ 該去的地方）會是 $1$ 所在的位置。這就是規則中「若格子非空」發生的時刻。
事實上，每填寫 $N$ 個數字就會遇到一次衝突。
衝突後的位移 (Shift)
當遇到衝突時，規則改為移動到 $(r+1, c)$ ，即向量 $v_2 = (1, 0)$ 。
這相當於開始了一條新的對角線。
讓我們觀察每條對角線起點的變化。
第一條對角線填了 $1 \dots N$ 。
第 $k$ 條對角線的起點相對於第 $k-1$ 條對角線的起點，其偏移量由 $N-1$ 次 $v_1$ 移動加上 $1$ 次 $v_2$ 移動組成：
$\Delta = (N-1)v_1 + v_2 = (N-1)(-1, 1) + (1, 0) \equiv (-1)(-1, 1) + (1, 0) = (1, -1) + (1, 0) = (2, -1) \pmod N$
這表示每填完 $N$ 個數，我們開始的新路徑起點會發生 $(2, -1)$ 的位移。

關鍵點： $N$ 為奇數的重要性

關注行座標的變化：每次位移 $+2$ 。
由於 $N$ 是奇數， $\gcd(2, N) = 1$ 。
這保證了 $0, 2, 4, \dots, 2(N-1)$ 在模 $N$ 下互不相同且遍歷了所有行。
因此，這 $N$ 條對角線（每條長度 $N$ ）也是互不重疊的，總共填滿了 $N^2$ 個格子。

複雜度分析

時間複雜度： $\mathcal{O}(N^2)$ ，每個格子填寫一次。
空間複雜度： $\mathcal{O}(N^2)$ ，用於儲存網格。

Code

def solve():
    N = int(input())

    ans = [[0] * N for _ in range(N)]

    r, c = 0, (N - 1) // 2
    for k in range(1, N * N + 1):
        ans[r][c] = k
        
        nr, nc = (r - 1) % N, (c + 1) % N
        if ans[nr][nc] == 0:
            r, c = nr, nc
        else:
            r, c = (r + 1) % N, c

    for row in ans:
        print(*row)

if __name__ == "__main__":
    solve()