TLE-oj Cup Round 4 - Xếp vua
Xem PDF
Nộp bài
Điểm:
1900 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
KING.inp
Output:
KING.out
Tác giả:
Dạng bài
Quân Vua trong bàn cờ vua có thể đi từ một ô đến 8 ô kề cạnh hoặc kề đỉnh với ô nó đang đứng. Hai quân Vua được xem là tấn công nhau khi và chỉ khi từ vị trí của quân Vua này có thể di chuyển đến vị trí của quân Vua kia trong một nước đi.
Nhiệm vụ của bạn là đếm số cách xếp những quân Vua trên bàn cờ n\times m sao cho không có hai quân Vua nào tấn công nhau (có thể xếp bao nhiêu cũng được, kể cả không xếp)
Input, Output và Subtasks
Input: (KING.inp)
- Dòng đầu tiên gồm duy nhất 2 số n và m (1\le n\le 10, 1\le m\le 10^3).
Output: (KING.out)
- Xuất ra duy nhất 1 số là kết quả của bài toán sau khi chia lấy dư cho 10^9+7.
Subtasks
- Subtask 1 (15\%): n,m \le 5.
- Subtask 2 (25\%): n,m \le 10.
- Subtask 3 (30\%): m \le 100.
- Subtask 4 (30\%): Không có ràng buộc gì thêm.
Sample
Input (KING.inp)
2 3
Output (KING.out)
11
Notes
Các cách xếp vua:
000 | 100 | 010 | 001 | 000 | 000 | 000 | 101 | 100 | 001 | 000
000 | 000 | 000 | 000 | 100 | 010 | 001 | 000 | 001 | 100 | 101
Sample
Input (KING.inp)
3 3
Output (KING.out)
35
Sample
Input (KING.inp)
4 7
Output (KING.out)
16334
Bình luận