互いに攻撃しない2つのナイト

互いに攻撃しない2つのナイト

各サイズの正方形の盤面で、2つのナイトを安全に配置できる組み合わせを数えます。

このチャレンジで学べること

各盤面サイズ k（1 から n まで）について、k × k の盤面上で2つのナイトが互いに攻撃できないように配置できる、異なる2マスの順不同の組み合わせの数を数えてください。ナイトは、縦横いずれか一方に2マス、もう一方に1マス移動します。

. x . x .
x . . . x
. . K . .
x . . . x
. x . x .

K はナイト、x は盤面上にある場合のそのナイトの移動先を示します。2つのナイトを入れ替えても別の配置とはみなしません。

two_knights(n) を実装してください。

n: 考慮する最大の盤面サイズ。

盤面サイズ 1 から n まで、それぞれの組み合わせ数を順に n 個返してください。

1 ≤ n ≤ 10,000。組み合わせ数は符号付き64ビット整数に収まります。

例 1

入力：
n = 3

期待される出力：
expected = [0, 6, 28]

入力：
long long n = 3;

期待される出力：
std::vector<long long> expected = {0, 6, 28};

入力：
long n = 3;

期待される出力：
long[] expected = new long[] {0, 6, 28};

1 × 1 の盤面には2つのナイトを置けません。2 × 2 の盤面には6通りの組み合わせがあり、攻撃し合うことはありません。3 × 3 の盤面には36通りの組み合わせがあり、そのうち8通りは攻撃し合うため、残りは28通りです。

例 2

入力：
n = 1

期待される出力：
expected = [0]

入力：
long long n = 1;

期待される出力：
std::vector<long long> expected = {0};

入力：
long n = 1;

期待される出力：
long[] expected = new long[] {0};

異なる2マスが必要ですが、盤面には1マスしかありません。

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

まず各盤面でのマスの順序なし組を数え、次にナイトが攻撃し合う組を引きます。

ヒント 2

どの盤面でも、2 by 3 または 3 by 2 の長方形に入る攻撃配置は決まった数だけです。

ヒント 3

1 by 1 や 2 by 2 のような端の盤面では、自然に0組になるようにします。

目安の計算量

時間 O(n)、追加メモリ O(1)

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。