【CSES】1072. Two Knights

題目連結

時間複雜度

• $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";
}