TLE-oj Cup Round 5 - Bàn cờ bằng nhau

Điểm: 1800 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: CHESS.inp

Output: CHESS.out

Tác giả:

huyhau6a2

Dạng bài

huyhau6a2 thích chơi cờ vua. Cậu đã tạo ra $n$ bàn cờ có kích thước $k\cdot k$ , được biểu diễn dưới dạng dãy $a$ 2 chiều với đặc điểm như sau:

$a[i][j]=0$ : Ô đó không có quân cờ
$a[i][j]=1$ : Ô đó có quân cờ

Tuy nhiên, sau khi chơi, có thể có các bàn cờ giống nhau. huyhau6a2 cần các bạn đếm số cặp bàn cờ giống nhau. Hai bàn cờ được coi là giống nhau khi một bàn cờ có thể xoay sao cho ra được bàn cờ còn lại

Input, Output và Subtasks

Input: (CHESS.inp)

Dòng đầu tiên gồm 2 số $n$ và $k$ ( $n\le 5\cdot 10^4,k\le 30$ )
Sau đó là $n$ block mô phỏng bàn cờ:
- Để dễ biểu diễn, bàn cờ sẽ được mô phỏng với mảng $b$ gồm $n$ số $x\text{ }(x<2^k)$
- Bàn cờ sẽ được biểu diễn dựa vào mảng $b$ như sau: Nếu bit thứ $j$ từ trái sang của phần tử thứ $i$ trong mảng $b$ bằng 1 thì $a[i][j]=1$ , ngược lại đặt $a[i][j]=0$

Output: (CHESS.out)

Xuất ra duy nhất 1 số là số cặp bàn cờ vua giống nhau

Subtasks

Subtask 1 $(20\%)$ : $n\le 5000,k\le 3$ .
Subtask 2 $(20\%)$ : $k\le 8$
Subtask 3 $(20\%)$ : $n\le 500$ .
Subtask 4 $(20\%)$ : $n\le 5000$
Subtask 5 $(20\%)$ : Không có ràng buộc gì thêm

Sample

Input (CHESS.inp)

Output (CHESS.out)

Notes

Bàn cờ thứ nhất:

010
101
000

Bàn cờ thứ hai:

010
001
010

Bàn cờ thứ ba:

110
001
100

Bàn cờ thứ tư:

101
001
010

Bình luận

Không có bình luận nào.