问题描述 :
We can generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as one of specific patterns occurs in the random string.
Your task is to predict the expected length of the generated string.
输入:
Standard input will contain multiple test cases.
First line is the number of case x.
Each test case consists of integer N (1<=N<=8) which is the number of letters used, and M (1<=M<=10) which is the number of patterns used. The following M lines contain the patterns which are non-empty strings consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 10.
输出:
Standard input will contain multiple test cases.
First line is the number of case x.
Each test case consists of integer N (1<=N<=8) which is the number of letters used, and M (1<=M<=10) which is the number of patterns used. The following M lines contain the patterns which are non-empty strings consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 10.
样例输入:
4
2 1
A
2 1
ABA
3 1
AAAAA
2 2
A
AA
样例输出:
2.00
10.00
363.00
2.00
