Pro.ID22551 TitleDecorations Title链接http://10.20.2.8/oj/exercise/problem?problem_id=22551 AC0 Submit0 Ratio- 时间&空间限制描述The Sultan of Sylvania loves throwing parties, because that gives him a reason to decorate the palace. He particularly likes decorations called streamers made up of di?rent beads strung together on a string and hung from the ceiling. Now, like most Sultans, he is very particular about everything, including these strung decorations. Specifically, he only likes certain combinations of beads to be used on the streamers. For example, if there are four di?rent types of beads - A, B, C and D - the Sultan might say "It pleases his highness that only the combinations ABB, BCA, BCD, CAB, CDD and DDA appear in the streamers at tonight's party". This, needless to say, puts a severe limit on the number of different streamers possible. For example, if the length of the streamers was 5, then the only possible streams of beads would be BCABB and BCDDA (strings such as ABBCA could not be used because BBC is not an approved combination). Since the Sultan likes variety, it is important to know the total number of streamers possible, given a length and the current bead combinations which tickle the Sultan's fancy. 输入Input will consist of multiple test cases. Each case will consist of two lines. The first line will contain three positive integers n, l and m, where n indicates the number of bead types, l is the length of the streamers and m indicates the number of bead combinations which the Sultan likes. The maximum values for n, l and m will be 26, 100 and 600, respectively. The next line will contain the m combinations. Each combination will be of the same length (between 1 and 10) and will be separated using a single space. All combinations will make use of only the uppercase letters of the alphabet. An input line of 0 0 0 will terminate input and should not be processed. 输出Description The Sultan of Sylvania loves throwing parties, because that gives him a reason to decorate the palace. He particularly likes decorations called streamers made up of di?rent beads strung together on a string and hung from the ceiling. Now, like most Sultans, he is very particular about everything, including these strung decorations. Specifically, he only likes certain combinations of beads to be used on the streamers. For example, if there are four di?rent types of beads - A, B, C and D - the Sultan might say "It pleases his highness that only the combinations ABB, BCA, BCD, CAB, CDD and DDA appear in the streamers at tonight's party". This, needless to say, puts a severe limit on the number of different streamers possible. For example, if the length of the streamers was 5, then the only possible streams of beads would be BCABB and BCDDA (strings such as ABBCA could not be used because BBC is not an approved combination). Since the Sultan likes variety, it is important to know the total number of streamers possible, given a length and the current bead combinations which tickle the Sultan's fancy. Input Input will consist of multiple test cases. Each case will consist of two lines. The first line will contain three positive integers n, l and m, where n indicates the number of bead types, l is the length of the streamers and m indicates the number of bead combinations which the Sultan likes. The maximum values for n, l and m will be 26, 100 and 600, respectively. The next line will contain the m combinations. Each combination will be of the same length (between 1 and 10) and will be separated using a single space. All combinations will make use of only the uppercase letters of the alphabet. An input line of 0 0 0 will terminate input and should not be processed. Output For each test case, output a single line indicating the number of possible streamers. All answers will be within the range of a 32-bit integer. Sample Input 4 5 6 ABB BCA BCD CAB CDD DDA 5 4 5 E D C B A 4 8 3 AA BB CC 0 0 0 Sample Output 2 625 3 Source 样例输入4 5 6 ABB BCA BCD CAB CDD DDA 5 4 5 E D C B A 4 8 3 AA BB CC 0 0 0 样例输出2 625 3 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-5 11:56 , Processed in 0.038271 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
