# 【CSES】1072. Two Knights

## [題目連結](https://cses.fi/problemset/task/1072/)

## **時間複雜度**

* $O(N)$

## **解題想法**

這題其實只要推出在 $k$ x $k$ 的棋盤上的所有可能解的公式是 $\frac{k^2(k^2-1)}{2}-4(k-1)(k-2)$ 就可以處理掉了，下面是公式的推導過程

### 推導過程

首先，我先假設出一張邊長為 $k$ 的棋盤如下


所以可以列出棋盤上任意放置兩個棋子的可能性有 **$\frac{k^2(k^2-1)}{2}$** 種

接著，我們知道一個騎士的可以攻擊的區域是這個的樣子


這幾個可以攻擊的區域可以簡單分成以下幾種類型

1. 直行型（共四個）


2. 橫列型（共四個）


同時也不難發現，這幾種可能性便是兩個棋子有可能會互相攻擊到的情形，所以可以推出兩個棋子互相攻擊到的所有情形是下面這幾種可能

$2$ x $(k-1)(k-2)$

 

而且在每一種情形中，都會有 A 攻擊 B，B 攻擊 A 的兩種情形，所以 $2$ x $(k-1)(k-2)$ 要再 x $2$

結合以上的敘述，可以推出在 $k$ x $k$ 的棋盤上的解就是

* **所有可能性減去會相互攻擊到的可能性** = **$\frac{k^2(k^2-1)}{2}-4(k-1)(k-2)$**

## **完整程式**

/* Question : CSES 1072. Two Knights */

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

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define f first
#define s second
#define int long long

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 1e8 + 50;
const int Mod = 1e9 + 7;
int n;

signed main(){
    opt;
    cin >> n;
    for( int i = 1 ; i <= n ; i++ ) 
      cout << ( i * i ) * ( i * i - 1 ) / 2 - 4 * ( i - 1 ) * ( i - 2 ) << "\n";
}