Đếm đường đi độ dài L

Buổi 36 — DP on DAG & Profile DP Dynamic Programming
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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$
Draft saved