題意#
題目給定一個整數 \( n \)。
我們需要計算：當棋盤大小從 \( 1 \times 1 \) 一路擴大到 \( n \times n \) 的時候，每一次把兩隻騎士（西洋棋裡的「馬」）隨機放上去，而且能保證它們「不會互相攻擊」的擺法有幾種。
思路#
這種題目如果硬去算「不互相攻擊」的擺法，會因為騎士位置的不同產生非常多種邊界限制，討論起來簡直是地獄。這時最經典的解法就是「正難則反」：用「全部的擺法」去扣掉「會互吃的擺法」。
首先，稍微想一下就知道，在一個大小為 \( k \times k \) 的棋盤上，總共有 \( k^2 \) 個格子。從這 \( k^2 \) 個格子中隨便挑 2 個出來放騎士，方法數就是高中數學教的組合計算： \( \frac{k^2(k^2-1)}{2} \) 種。
接下來我們來抓那些會互相攻擊的組合。回想一下西洋棋騎士走的是「L 型」，如果你在紙上畫一個 L 型路徑，會發覺這其實剛好可以被框在一個「 \( 2 \times 3 \) 」或者「 \( 3 \times 2 \) 」的小矩形裡面。而且更妙的是，每一個這樣的小矩形剛好都可以提供「兩種」騎士互吃的方法（因為有兩條對角線）。
那麼在一個 \( k \times k \) 的棋盤裡，總共能塞入幾塊 \( 2 \times 3 \) 和 \( 3 \times 2 \) 的小方框呢？
算一下長寬的容納量就知道會各有 \( (k-1)(k-2) \) 塊。這兩種方向加總起來就是 \( 2(k-1)(k-2) \) 塊。
既然每塊小矩形都會引發兩種互吃擺法，那總共互相攻擊的次數就是這坨東西乘上 2，也就是 \( 4(k-1)(k-2) \)。
最後，把剛剛算出來的全空間跟互吃組合相減，公式就長出來了！
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n;
cin >> n; // 讀取棋盤的最大邊長 n
// 依序計算從小到大 nxn 棋盤的合法擺放方法數
for (int i = 1; i <= n; i++) {
// 全空間 (所有隨機擺法) 減去 會互相攻擊的擺法
cout << i*i*(i*i-1)/2 - 4*(i-1)*(i-2) << '\n';
}
}
