TopCoder SRM 599 - 950: SimilarNames

Problem Statement

输入n个字符串，现在需要给它们从0到n - 1标号，
满足m条形如标号为a[i]的字符串是标号为b[i]的字符串的前缀的限制。
求标号方案数，模10^9+7输出。
n,字符串长度 <= 50, m <= 8。

Fox Ciel has a list of names on her computer. In this problem, a name is simply a non-empty string of lowercase letters. All names in her list are distinct.

One day, when she left her seat, she forgot to lock her computer. Then, Lun the mischievous dog appeared, and randomly shuffled the order of the names in her list.

Now, Ciel has to restore the original order of names using her memory. You are given a String[] names, along with two int[]s info1 and info2. names contains all names in the shuffled list in the order they appear. info1 and info2 describes Ciel's memory of the original list. She remembers that, for each valid i, the info1[i]-th (0-indexed) name in the original list was a prefix of the info2[i]-th name.

Let X be the number of possible orders of the names in the original list that are consistent with Ciel's memory. Calculate and return the value (X modulo 1,000,000,007). X can be 0, which means Ciel's memory is inconsistent with the names in the list.

Definition

Class SimilarNames
Method count
Parameters vector<string> , vector<int> , vector<int>
Returns int
Method signature int count(vector<string> names, vector<int> info1, vector<int> info2)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

A prefix of a string is the result of erasing zero or more characters from the right end of that string.

Constraints

names will contain between 2 and 50 elements, inclusive.
Each element of names will contain between 1 and 50 characters, inclusive.
Each character of each element of names will be a lowercase letter ('a'-'z').
Elements of names will be distinct.
info1 and info2 will each contain between 0 and 8 elements, inclusive.
info1 and info2 will contain the same number of elements.
Each element of info1 and info2 will be between 0 and n-1, inclusive, where n is the number of elements in names.
For each valid i, info1[i] and info2[i] will be distinct.
All pairs (info1[i], info2[i]) will be distinct.

Test cases

input
- names { "kenta", "kentaro", "ken" }
- info1 { 0 }
- info2 { 1 }
output
Returns 3
note
Here, Ciel's list contains 3 names. She remembers that the 0-th name was a prefix of the 1-th name in the original list. Here are the all possible orders of names in the original list:
- ken, kenta, kentaro
- ken, kentaro, kenta
- kenta, kentaro, ken
Note that it is possible that the order of the names in the original list coincides with that of the shuffled list.
input
- names { "hideo", "hideto", "hideki", "hide" }
- info1 { 0, 0 }
- info2 { 1, 2 }
output
Returns 6

note

She remembers that the 0-th name was a prefix of both the 1-th name and 2-th name in the original list. The only thing we can be sure is that the 0-th name was "hide".
input
- names { "aya", "saku", "emi", "ayane", "sakura", "emika", "sakurako" }
- info1 { 0, 1, 3, 5 }
- info2 { 1, 2, 4, 6 }
output
Returns 2
note
This time, she remembers many facts. The only possible original orders are:
- saku, sakura, sakurako, aya, ayane, emi, emika
- saku, sakura, sakurako, emi, emika, aya, ayane
input
- names { "taro", "jiro", "hanako" }
- info1 { 0, 1 }
- info2 { 1, 0 }
output
Returns 0

note

According to her memory, the 0-th name and the 1-th name in the original list must be the same, but actually all names are distinct. Her memory is inconsistent.
input
- names { "alice", "bob", "charlie" }
- info1 { }
- info2 { }
output
Returns 6

note

Unfortunately she remembers nothing in this case.
input
- names { "ryota", "ryohei", "ryotaro", "ryo", "ryoga", "ryoma", "ryoko", "ryosuke", "ciel", "lun", "ryuta", "ryuji", "ryuma", "ryujiro", "ryusuke", "ryutaro", "ryu", "ryuhei", "ryuichi", "evima" }
- info1 { 17, 5, 6, 13, 5 }
- info2 { 9, 2, 14, 17, 14 }
output
Returns 994456648

back to the menu