Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.