trang chủ / đề bài / icpc20_nat_h

Đường lên đỉnh Fansipan

Đề bài

Mô tả

Năm 3030, Đườ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 n từ hàng ngang. Các chữ cái đầu tiên của n 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ó 4 từ hàng ngang là invite, cat, party và cow. Các chữ cái đầu của 4 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 n từ hàng ngang. Từ thứ i phải có đúng wi ký tự.
  • Bạn được cho một từ điển gồm d từ. Mỗi từ hàng ngang và thông điệp ẩn đều phải nằm trong từ điển.
  • 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 n từ hàng ngang khác nhau.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên T: số bộ dữ liệu. Tiếp theo là T bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu tiên chứa một số nguyên dương n: số từ hàng ngang.
  • Dòng thứ hai chứa đúng n số nguyên dương w1,w2,…,wn (1≤wi≤50), trong đó wi là độ dài của từ hàng ngang thứ i.
  • Dòng thứ ba chứa một số nguyên dương d.
  • d dòng tiếp theo, mỗi dòng chứa một từ trong từ điển. Mỗi từ gồm từ 1 đến 50 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 109+7.

Ràng buộc

  • Tổng n qua tất cả các bộ dữ liệu không vượt quá 105.
  • Tổng d qua tất cả các bộ dữ liệu không vượt quá 105.
  • Tổng độ dài của mọi từ trong mọi bộ dữ liệu không vượt quá 5·105.
  • 1≤wi≤50.

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 4 để 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0