VMROOK - Xe
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Cho một bàn cờ vuông kích thước N*N, trên đó có một số ô cấm. Bạn cần đặt N quân xe lên đấy sao cho:
- Trên mỗi ô của bàn cờ, chỉ có tối đa 1 quân xe
- Không có quân xe nào được đặt lên các ô cấm
- Không có 2 quân xe nào có thể ăn được nhau (cùng hàng hoặc cùng cột). Chú ý rằng các quân xe có thể đi xuyên qua ô cấm.
Đếm số cách đặt N quân xe lên bảng, theo modulo 2 (mod 2).
Input
- Dòng 1: Số nguyên dương T - số bộ test.
-
Tiếp theo là T bộ test, mỗi bộ test gồm:
- Dòng 1: Số nguyên dương N
- Tiếp theo là N dòng, dòng thứ i gồm N số nguyên. Số nguyên thứ j trên dòng i là 0 nếu ô tương ứng là ô cấm và bằng 1 trong trường hợp ngược lại.
Output
Gồm T dòng, mỗi dòng là một số nguyên duy nhất là số cách đặt quân xe theo modulo 2.
Giới hạn
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 250
- Trong 20% số test, N ≤ 15
Chấm điểm
- Bài của bạn sẽ được chấm trên thang điểm 100. Điểm mà bạn nhận được sẽ tương ứng với % test mà bạn giải đúng.
- Trong quá trình thi, bài của bạn sẽ chỉ được chấm với 1 test ví dụ có trong đề bài.
- Khi vòng thi kết thúc, bài của bạn sẽ được chấm với bộ test đầy đủ.
Example
Input: 2 3 1 0 1 0 1 1 1 1 1 2 1 0 0 1 Output: 1 1
Giải thích
- Trong test đầu tiên, có 3 cách xếp. Bạn cần in ra 3 mod 2 = 1
- Trong test thứ hai, có duy nhất 1 cách xếp. Bạn cần in ra 1 mod 2 = 1
- Người up: voj