Đếm đường đi Hamilton

Buổi 33 — Bitmask DP & SOS DP
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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
Draft saved