902 . Betrayal at House on the Hill
TopCoder
Description
One night, you and your friends are having an adventure in a haunted house on a hill.
You walk from one room to another, pass the doors, and look for some interesting things.
As you explore the house, you encounter spirits and frightening omens that foretell your fate.
Secretly, one of your friend betrays you and becomes evil.
He is casting magic spells and curses on all of you to sacrifice you to the dark lord.
You must defeat the traitor before it is too late!
To defeat the traitor, you have holy key phrase.
The evil traitor cannot sustain the magic of the holy key phrase.
Once you correctly spell the key phrase using proper magic,
the evil traitor will suddenly be shattered and vanish.
The magic to spell the holy key phrase works in this way:
There is a symbol on each door.
A symbol is an uppercase or lower case English letter.
Every time you pass a door, the symbol on that door is appended to the phrase that you are spelling.
At any time if the phrase you sell is exactly the same as the holy key phrase,
the magic happens!
Now, given the map of the house and the holy key phrase,
please compute how many ways to spell the holy key phrase.
You can start spelling from any room in this house.
Two ways are considered different if different doors are used at some symbols.
Since this number may be large, you only need to compute this number modulo an integer P.
Input Format
The first line contains an integer T indicating the number of test cases.
Each test case begins with a line containing three integers, N, M and P.
N is the number of rooms, and M is the number of doors.
The next line is a string S, the holy key phrase.
Following that there will be M lines, each specifies a door in this house.
The i-th line has two integers, a_i and b_i, and one character c_i.
This means that you can go from room a_i to room b_i via the i-th door, and the symbol on this door is c_i.
Notice that you are not able to go from room b_i to room a_i via the i-th door.
1 <= N <= 1000
1 <= M <= 5000
0 <= a_i, b_i < N
0 < P < 230
The length of S is less than 5000.
Only English letters will exist in S and c_i, and these letters are case-sensitive.
Output Format
Please output one line per test case.
This line contains the number of ways to spell the holy key phrase modulo P.
Sample Input 1
2 4 4 10000 ABABABAB 1 2 A 2 3 B 3 0 A 0 1 B 2 4 10000 xyxy 1 0 x 0 1 y 0 1 y 1 0 x
Sample Output 1
2 16
Hints
If you like these kind of stories,
probably you would like the board game "Betrayal at House on the Hill".
Problem Source
Migrated from old NTUJ.
Ferng
Subtasks
| No. | Testdata Range | Score |
|---|