Hai quân mã (Two Knights)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Xét bàn cờ vuông kích thước $k\times k$. Cần đặt hai quân mã lên hai ô khác nhau sao cho không quân nào có thể tấn công quân còn lại bằng một nước đi mã trong cờ vua. Quân mã đi hai ô theo một hướng ngang hoặc dọc và một ô theo hướng vuông góc. Hai cách đặt chỉ khác thứ tự đặt quân mã không được tính là hai cách khác nhau. Cho $n$. Với từng kích thước $k=1,2,\ldots,n$, hãy tính số cách đặt hợp lệ.

Input

Một dòng chứa số nguyên dương $n$, kích thước bàn cờ lớn nhất cần xét.

Output

In $n$ dòng. Dòng thứ $k$ chứa số cách đặt hai quân mã không tấn công nhau trên bàn cờ $k\times k$.

Subtask

• Subtask 1 (20%): $1\\le n\\le20$.
• Subtask 2 (30%): $1\\le n\\le200$.
• Subtask 3 (50%): $1\\le n\\le10000$.

Ví dụ

Ví dụ 1

Input:

3

Output:

0
6
28

Giải thích: Bàn $1\times1$ chỉ có một ô nên không đặt được hai quân: $0$ cách. Bàn $2\times2$ có $4$ ô, chọn hai ô được $4\cdot3/2=6$ cách; quân mã không có nước tấn công nào nằm trong bàn. Bàn $3\times3$ có $9\cdot8/2=36$ cặp ô và $8$ cặp tấn công; còn $36-8=28$ cách hợp lệ.

Ví dụ 2

Input:

1

Output:

0

Giải thích: Chỉ có một ô, do đó không thể đặt đồng thời hai quân mã trên hai ô phân biệt.

Ví dụ 3

Input:

4

Output:

0
6
28
96

Giải thích: Với $k=4$ có $16$ ô, tổng số cặp là $16\cdot15/2=120$. Số cặp quân mã tấn công là $4\cdot3\cdot2=24$, vì vậy $120-24=96$. Ba dòng trước ứng với $k=1,2,3$.