Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
TPJOUR - JOURNEY |
Cho 1 đồ thị có N đỉnh, M cạnh 2 chiều. 2 đỉnh được nối với nhau nhiều nhất là 1 cạnh.
1 đường đi là 1 chuỗi các đỉnh sao cho các đỉnh kề nhau có cạnh nối với nhau.
1 đường đi đẹp phải thỏa mãn :
- Chuỗi đỉnh có độ dài là D.
- Các đỉnh từ 1 đến K phải xuất hiện ít nhất 1 lần.
Yêu cầu : Tính số đường đi đẹp mod 1000000009.
Giới hạn N<=20, D<=1000000000. K<=7.
Input
- 4 số N,M,K,D
- M dòng mỗi dòng 2 số u,v cho biết có đường đi 2 chiều cạnh nỗi 2 đỉnh u và v
Output
- Số đường đi đẹp mod 1000000009.
Sample input
4 4 2 3
1 2
2 3
3 1
2 4
Sample output
10
#Giải thích
Các đường đi có thể là :
- 1_2_1
- 1_2_3
- 1_2_4
- 1_3_2
- 2_1_2
- 2_1_3
- 2_3_1
- 3_1_2
- 3_2_1
- 4_2_1
Được gửi lên bởi: | dqd |
Ngày: | 2009-09-18 |
Thời gian chạy: | 1s-1.096s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET |
Nguồn bài: | Sưu tầm |
hide comments
2019-10-01 14:52:18
Hint : Kiểm soát K = bitmask, đếm số đường đi D bằng ma trận, dùng bao hàm loại trừ. |
|
2019-10-01 03:35:38
Mod la 10^9 + 9 nhe <(") Dm de <(") |
|
2009-09-22 15:54:14 Saturn
ps co the noi rong thoi gian mot chut khong Last edit: 2009-09-23 14:59:51 |