Đường lên đỉnh Fansipan
Đề bài
Mô tả
Năm , Đường lên đỉnh Fansipan là chương trình trò chơi truyền hình được yêu thích nhất Việt Nam.
Trong chương trình này, bốn thí sinh được cho một ô chữ. Ô chữ gồm từ hàng ngang. Các chữ cái đầu tiên của từ này, đọc từ trên xuống dưới, tạo thành một thông điệp ẩn. Thí sinh đầu tiên tìm ra thông điệp ẩn sẽ thắng.
Ví dụ, một ô chữ có từ hàng ngang là invite, cat, party và cow. Các chữ cái đầu của từ này tạo thành thông điệp ẩn icpc.
Năm nay, bạn được giao nhiệm vụ tạo một ô chữ cho Đường lên đỉnh Fansipan với các yêu cầu sau:
- Có đúng từ hàng ngang. Từ thứ phải có đúng ký tự.
- Bạn được cho một từ điển gồm từ. Mỗi từ hàng ngang và thông điệp ẩn đều phải nằm trong từ điển.
- từ hàng ngang và thông điệp ẩn phải đôi một khác nhau.
Là một lập trình viên giỏi, việc tạo một ô chữ thỏa mãn các yêu cầu trên rất dễ với bạn. Nhưng bạn muốn biết có bao nhiêu cách tạo ô chữ khác nhau. Hai ô chữ được coi là khác nhau nếu có ít nhất một trong từ hàng ngang khác nhau.
Dữ liệu vào
Dòng đầu tiên chứa một số nguyên : số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ có dạng:
- Dòng đầu tiên chứa một số nguyên dương : số từ hàng ngang.
- Dòng thứ hai chứa đúng số nguyên dương (), trong đó là độ dài của từ hàng ngang thứ .
- Dòng thứ ba chứa một số nguyên dương .
- dòng tiếp theo, mỗi dòng chứa một từ trong từ điển. Mỗi từ gồm từ đến chữ cái tiếng Anh in thường. Không có hai từ nào giống nhau.
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên: số cách khác nhau để tạo ô chữ, theo modulo .
Ràng buộc
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
- Tổng qua tất cả các bộ dữ liệu không vượt quá .
- Tổng độ dài của mọi từ trong mọi bộ dữ liệu không vượt quá .
- .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 4 6 3 5 3 5 invite icpc party cat cow 4 6 3 5 3 4 invite party cat cow |
2 0 |
Bộ thứ nhất: thông điệp ẩn phải là icpc; hai ô chữ là (invite, cat, party, cow) và (invite, cow, party, cat). Bộ thứ hai: từ điển không có từ nào dài để làm thông điệp ẩn. |
| 1 2 2 2 4 ab aa ba bb |
4 | Ví dụ bổ sung (không có trong đề gốc). Thông điệp ẩn ab cho (aa, ba) và (aa, bb); thông điệp ẩn ba cho (bb, aa) và (bb, ab). Thông điệp ẩn aa hay bb đều cần hai từ hàng ngang khác nhau bắt đầu bằng cùng một chữ và khác thông điệp, nhưng chỉ còn một từ như vậy. |
Bình luận