Bài 1 Tô màu (6 điểm)
An thường dành ít thời gian rảnh rỗi của mình vẽ tranh. Cô thích sử dụng bút lông và một bảng màu chứa K màu sắc. Hùng muốn kiểm tra tài năng của An nên đưa cho An cuốn sách tô màu mới để tô màu. Cuốn sách tô màu có chứa N hình ảnh 1, 2, ..., N.
An đã quyết định sơn mỗi hình ảnh chính xác một màu sắc trong K màu sắc có thể từ bảng màu mình. Tuy nhiên, cô ấy rất thích những điều đầy màu sắc. Cô đã chọn N số fi và quyết định tô hình ảnh đánh số i khác biệt so với những hình ảnh số fi, trừ khi fi = i. Nếu fi = i, có nghĩa là cô có thể tô hình ảnh số fi màu nào tùy thích, miễn là tất cả các điều kiện khác đã được đáp ứng.
An muốn biết số cách có thể để tô màu cuốn sách của Hùng và An đang rất cần sự giúp đỡ của bạn! Tính số cách có thể để tô màu cuốn sách.
Kết quả đầu ra có thể rất lớn, in câu trả lời theo modul 1 000 000 007.
Dữ liệu: Vào từ file văn bản Paleta.Inp
- Dòng đầu tiên chứa số nguyên dương N, K (1 <= N, K <= 1 000 000).
- Dòng sau chứa N số fi (1 <= fi <= N)
Kết quả: Ghi vào tệp văn bản Paleta.Out
Dòng đầu tiên và duy nhất chứa các số cách có thể để tô màu cuốn sách .
Ví dụ
Paleta.Inp Paleta.Inp Paleta.Inp Paleta.Inp
2 3
2 1
3 4
2 3 1
3 4
2 1 1
3 4
1 1 2
Paleta.Out Paleta.Out Paleta.Out Paleta.Out
6 24 36 36

Giải thích ví dụ đầu tiên: An có ba màu sắc và tô hình ảnh số 2 không cùng màu sắc như hình số 1. Ta có thể tô theo cách sau (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), trong đó số đầu tiên trong ngoặc đơn đại diện cho màu sắc của hình ảnh đầu tiên và số thứ hai là màu sắc của hình ảnh thứ hai.
Giải thích ví dụ thứ tư: An có bốn màu sắc. Không có điều kiện liên quan đến hình ảnh đầu tiên, nó có thể được sơn màu nào cũng được. Hình thứ hai phải khác so với hình 1, và hình thứ ba khác với hình thứ hai. Điều đó có nghĩa rằng hai hình ảnh có thể được tô màu trong 3 màu còn lại. Điều này cho chúng ta có tổng cộng 36 cách tô
Ràng buộc
Có 60% tổng điểm, tất cả các số fi sẽ khác nhau
Câu 2 TËp m· (7 điểm)
Cho kh«ng qu¸ 20 x©u kÝ tù, mçi x©u cã ®é dµi kh«ng qu¸ 10 chØ gåm c¸c ch÷ c¸i a..z. H·y t×m mét x©u cã ít nhất hai c¸ch biÓu diÔn kh¸c nhau b»ng c¸c x©u ®· cho b»ng c¸ch ghÐp liªn tiÕp (Mçi x©u chØ ®­îc dïng một lÇn).
Dữ liệu: CODE.INP
· Dßng ®Çu ghi N – sè x©u con
· N dßng tiÕp theo, mçi dßng ghi mét x©u con.
Kết quả: CODE.OUT
· Dßng ®Çu ghi 1/0 nÕu tån t¹i/ kh«ng tån t¹i x©u tháa m·n.
· Nếu dßng ®Çu ghi 1, ta lµm c¸c b­íc tiÕp theo :
· Dßng 2 ghi x©u t×m ®­îc
· Dßng 3 ghi K - sè c¸ch biÓu diÔn (>=2)
· K dßng tiÕp theo, mçi dßng ghi 1 c¸ch biÓu diÔn b»ng c¸ch ghi liªn tiÕp c¸c chØ sè c¸c x©u con trong c¸ch biÓu diÔn ®ã.
VD :
CODE.INP CODE.OUT CODE.INP CODE.OUT
4
ab
c
bc
abc
1
abc
2
1 2
4
2
aaa
bbb
0


Ràng buộc
Có 30% số test ứng với 30% số điểm của bài có N ≤ 10
Có 30% số test ứng với 30% số điểm của bài có N ≤ 15
Có 40% số test ứng với 30% số điểm của bài có N ≤ 20
Bài 3 Ca nhạc

­Trong cuộc thi các tiết mục ca nhạc, N nhóm nghệ sĩ (được đánh số từ 1 đến N) đồng thời trình diễn những tiết mục của mình tại N địa điểm gần nhau, thời gian kết thúc của nhóm thứ iti. Để thu hút khách đến xem, mỗi nhóm tặng quà cho khách vào xem, trị giá tặng là zi, với điều kiện thời gian khách xem tối thiểu là d đơn vị thời gian.
Hãy lập trình chọn ra các nhóm cần xem sao cho tổng trị giá quà tặng là lớn nhất. Giả sử thời gian bắt đầu của tất cả các nhóm là 0 và thời gian di chuyển giữa các địa điểm là không đáng kể.
Dữ liệu vào từ file văn bản MUSIC.INP với cấu trúc như sau:
Dòng đầu tiên là 2 số nguyên dương N và d (N≤1000)
Dòng thứ hai là dãy số nguyên dương ti, (i=1, 2, ..., N)
Dòng thứ 3 là dãy số nguyên dương zi, (i=1, 2, ..., N)
Kết quả ghi ra file MUSIC.OUT
Dòng đầu là tổng giá trị quà tặng
Dòng sau là dãy thứ tự các nhóm cần xem
Ví dụ
MUSIC.IN MUSIC.OUT
7 1
2 1 4 1 5 2 4
100 10 15 27 52 19 36
230
4 1 3 7 5

Ràng buộc
Có 30% số test ứng với 30% số điểm của bài có N ≤ 100
Có 30% số test ứng với 30% số điểm của bài có N ≤ 500
Có 40% số test ứng với 30% số điểm của bài có N ≤ 1000
.................HẾT.................