Trie Sharding

Một tập hợp các chuỗi \(S\) có thể được lưu trữ hiệu quả trong một trie. Một trie là một cây có gốc, trong đó mỗi nút đại diện cho một tiền tố của mọi chuỗi trong \(S\), không trùng lặp.

Ví dụ, nếu \(S\) là "AAA", "AAB", "AB", "B", trie tương ứng sẽ chứa 7 nút tương ứng với các tiền tố "", "A", "AA", "AAA", "AAB", "AB", và "B".

Tôi có một máy chủ chứa \(S\) trong một trie lớn. Không may, \(S\) đã trở nên rất lớn và tôi gặp khó khăn khi lưu trữ mọi thứ trong bộ nhớ trên một máy chủ. Để giải quyết vấn đề này, tôi muốn chuyển sang lưu trữ \(S\) trên \(N\) máy chủ riêng biệt. Cụ thể, \(S\) sẽ được chia thành các tập con không giao nhau và không rỗng \(T_1, T_2, \dots, T_N\), và trên mỗi máy chủ \(i\), tôi sẽ xây dựng một trie chỉ chứa các chuỗi trong \(T_i\). Nhược điểm của cách tiếp cận này là tổng số nút trên tất cả \(N\) trie có thể tăng lên. Tệ hơn nữa, tôi không thể kiểm soát cách tập hợp các chuỗi được chia nhỏ!

Ví dụ, giả sử "AAA", "AAB", "AB", "B" được chia vào hai máy chủ, một máy chứa "AAA" và "B", và máy kia chứa "AAB", "AB". Khi đó trie trên máy chủ thứ nhất sẽ cần 5 nút ("", "A", "AA", "AAA", "B"), và trie trên máy chủ thứ hai cũng sẽ cần 5 nút ("", "A", "AA", "AAB", "AB"). Trong trường hợp này, tôi sẽ cần tổng cộng 10 nút trên hai máy chủ, trái ngược với 7 nút nếu tôi có thể để mọi thứ trên chỉ một máy chủ.

Cho một cách phân bổ các chuỗi vào \(N\) máy chủ, tôi muốn tính tổng số nút lớn nhất có thể có trên tất cả các máy chủ trong trường hợp xấu nhất, và khả năng điều đó xảy ra là bao nhiêu. Sau đó, tôi có thể quyết định xem kế hoạch của mình là tốt hay quá rủi ro.

Cho \(S\) và \(N\), số lượng nút lớn nhất mà tôi có thể nhận được là bao nhiêu? Ngoài ra, có bao nhiêu cách chọn \(T_1, T_2, \dots, T_N\) để số lượng nút là tối đa? Lưu ý rằng \(N\) máy chủ là khác nhau -- nếu một chuỗi xuất hiện trong \(T_i\) ở một cách sắp xếp và trong \(T_j\) (\(i \neq j\)) ở một cách sắp xếp khác, thì hai cách sắp xếp đó được coi là khác nhau. Hãy in ra phần dư của số cách sắp xếp có thể sau khi chia cho \(1,000,000,007\).

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ dữ liệu, \(T\). \(T\) bộ dữ liệu tiếp theo. Mỗi bộ dữ liệu bắt đầu bằng một dòng chứa hai số nguyên cách nhau bởi dấu cách: \(M\) và \(N\). \(M\) dòng tiếp theo, mỗi dòng chứa một chuỗi trong \(S\).

Dữ liệu ra

Đối với mỗi bộ dữ liệu, hãy xuất một dòng chứa "Case #\(i\): \(X\) \(Y\)", trong đó \(i\) là số thứ tự của bộ dữ liệu (bắt đầu từ 1), \(X\) là số lượng nút tối đa trong trường hợp xấu nhất trên tất cả các trie kết hợp lại, và \(Y\) là số cách (theo mô-đun \(1,000,000,007\)) để phân bổ các chuỗi vào các máy chủ sao cho tổng số nút là \(X\).

Ràng buộc

• \(1 \le T \le 100\).
• Các chuỗi trong \(S\) sẽ chỉ chứa các chữ cái tiếng Anh in hoa.
• Các chuỗi trong \(S\) đều phân biệt.
• \(N \le M\).

Phân nhóm

• Small dataset:

  • \(1 \le M \le 8\).
  • \(1 \le N \le 4\).
  • Mỗi chuỗi trong \(S\) có độ dài từ 1 đến 10 ký tự.

  • Large dataset:

  • \(1 \le M \le 1000\).

  • \(1 \le N \le 100\).
  • Mỗi chuỗi trong \(S\) có độ dài từ 1 đến 100 ký tự.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
4 2
AAA
AAB
AB
B
5 2
A
B
C
D
E

Case #1: 10 8
Case #2: 7 30

Nguồn

Google Code Jam 2014, Vòng 2, bài Trie Sharding.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.