Đếm đường đi độ dài L
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Cho một đồ thị có hướng không chu trình (DAG) gồm $N$ đỉnh, $M$ cạnh có hướng và một số nguyên $L$. Hãy đếm tổng số đường đi có hướng có độ dài đúng bằng $L$ cạnh (có thể bắt đầu ở bất kỳ đỉnh nào và kết thúc ở bất kỳ đỉnh nào), lấy phần dư khi chia cho $10^9 + 7$.
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên $N, M, L$.
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ mô tả cạnh có hướng từ $u$ đến $v$.
Dữ liệu ra
- In ra số lượng đường đi có độ dài đúng $L$ cạnh theo modulo $10^9 + 7$.
Ví dụ
| Input | Output |
|---|---|
| 4 4 2\n1 2\n1 3\n2 4\n3 4 | 2 |
Giới hạn
- $1 \le N \le 2000$
- $0 \le M \le 5000$
- $1 \le L \le 100$
Community Discussion