Đếm đường đi Hamilton
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một đơn đồ thị có hướng gồm $N$ đỉnh (đánh số từ $1$ đến $N$) và $M$ cung. Hãy đếm số lượng đường đi Hamilton khác nhau trên đồ thị (đường đi qua tất cả $N$ đỉnh, mỗi đỉnh đúng một lần; có thể bắt đầu và kết thúc tại bất kỳ đỉnh nào). In ra kết quả chia dư cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N$ và $M$ ($1 \le N \le 18$, $0 \le M \le N(N-1)$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le N$, $u \ne v$) biểu thị cung có hướng từ $u$ đến $v$.
Dữ liệu ra
- In ra một số nguyên duy nhất là số đường đi Hamilton chia dư cho $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 4 5 1 2 2 3 3 4 1 3 2 4 |
1 |
| 3 6 1 2 2 1 1 3 3 1 2 3 3 2 |
6 |
Giới hạn
- $1 \le N \le 18$
- Không có đa cung hay khuyên
Community Discussion