제네릭 포커

시간 제한1초메모리 제한128 MB

요약

각 등급이 N장씩 있는 M개 등급 카드에서 L장을 뽑을 때, 별표와 플러스로 이동한 변수로 이루어진 패턴에 맞는 손의 확률을 기약분수로 출력한다.

난이도: 어려움10점 중 8점
유형: 조합론, 완전 탐색, 수학, 구현
정답자: 아직 제출이 없습니다

문제

$N \times M$ 장의 카드로 이루어진 덱이 있습니다. 각 카드에는 랭크가 하나 적혀 있으며, 랭크는 $1$ 부터 $M$ 까지의 정수입니다. 덱에는 각 랭크마다 정확히 $N$ 장의 카드가 들어 있습니다. 여기서는 랭크가 $m$ 인 카드를 간단히 $m$ 으로 표기합니다.

덱에서 무작위로 $L$ 장의 카드를 뽑아 하나의 핸드를 만듭니다. 뽑힌 핸드가 주어진 패턴과 일치하면 보너스를 받습니다. 패턴의 문법은 다음과 같습니다.

hand_pattern = card_pattern1 ' ' card_pattern2 ' ' ... ' ' card_patternL
card_pattern = '*' | var_plus
var_plus = variable | var_plus '+'
variable = 'a' | 'b' | 'c'

hand_pattern: 핸드의 서로 다른 카드들을 패턴의 각 card_pattern에 일대일로 대응시켜 모든 card_pattern이 자신에게 대응된 카드와 일치할 수 있으면, 그 핸드는 hand_pattern과 일치합니다.
card_pattern
- card_pattern이 별표 *이면 임의의 카드와 일치합니다.
- 문자 a, b, c는 변수이며, 같은 변수의 모든 등장은 같은 랭크의 카드와 일치해야 합니다. 변수 뒤에 더하기 기호 +가 붙으면, 그 card_pattern은 (해당 변수에 대응된 랭크) + (더하기 기호의 개수)에 해당하는 랭크의 카드와 일치합니다.
- 어떤 변수 뒤에 $k$ 개의 +가 붙은 card_pattern이 패턴에 등장하면, 같은 변수에 대해 $0$ 개부터 $k-1$ 개까지의 +가 붙은 card_pattern도 모두 패턴에 등장한다고 가정할 수 있습니다. 예를 들어 a+++가 등장하면 a, a+, a++도 함께 등장합니다.

서로 다른 변수가 어떤 랭크를 뜻하는지에 대한 제약은 없습니다. 예를 들어 a와 b는 같은 랭크의 카드와 일치할 수도 있고, 그렇지 않을 수도 있습니다.

몇 가지 예를 봅시다. 패턴

a * b a b

은 다음 핸드와 일치합니다. 이때 a와 b는 각각 $3$ 과 $10$ 을 (또는 $10$ 과 $3$ 을) 뜻합니다.

3 3 10 10 9

같은 패턴은 다음 핸드와도 일치하며, 이 경우 a와 b는 모두 $3$ 을 뜻합니다.

3 3 3 3 9

패턴

a a+ a++ a+++ a++++

는 다음 핸드와 일치하며, 이때 a는 $4$ 를 뜻합니다.

4 5 6 7 8

주어진 hand_pattern에 대해, 덱에서 무작위로 뽑은 핸드가 그 패턴과 일치할 확률을 구하는 프로그램을 작성하세요.

입력

입력은 여러 개의 데이터셋으로 이루어져 있습니다. 각 데이터셋의 형식은 다음과 같습니다.

N M L
card_pattern1 card_pattern2 ... card_patternL

첫 번째 줄에는 세 양의 정수 $N$ , $M$ , $L$ 이 주어집니다. $N$ 은 각 랭크의 카드 장수, $M$ 은 랭크의 개수, $L$ 은 한 핸드의 카드 장수입니다. 제약 조건은 다음과 같습니다.

$1 \le N \le 7$
$1 \le M \le 60$
$1 \le L \le 7$
$L \le N \times M$

두 번째 줄에는 $L$ 개의 card_pattern으로 이루어진 hand_pattern이 공백으로 구분되어 주어집니다.

입력의 끝은 공백으로 구분된 세 개의 $0$ (0 0 0)만 있는 줄로 표시됩니다. 이 줄은 처리하지 않습니다.

출력

각 데이터셋마다, 핸드가 hand_pattern과 일치할 확률을 기약분수 $p/q$ 형태로 한 줄에 출력하세요. 여기서 $q \ge 1$ 이고 $\gcd(p, q) = 1$ 입니다. 확률이 $0$ 이면 0/1을, 확률이 $1$ 이면 1/1을 출력합니다. 각 줄에는 이 분수 외의 다른 문자를 포함하지 마세요.

예제5

예제 1

입력

1 1 1
a
3 3 4
a+ * a *
2 2 3
a a b
2 2 3
* * *
2 2 3
* b b
2 2 2
a a
2 3 3
a a+ a++
2 6 6
a a+ a++ b b+ b++
4 13 5
a a * * *
4 13 5
a a b b *
4 13 5
a a a * *
4 13 5
a a+ a++ a+++ a++++
4 13 5
* * * * *
4 13 5
a a a b b
4 13 5
a a a a *
7 60 7
a b a b c c *
7 60 7
* * * * * * *
7 60 7
a a+ a++ a+++ a++++ a+++++ a++++++
1 14 4
b a+ a a
0 0 0

예상 출력

1/1
37/42
1/1
1/1
1/1
1/3
2/5
4/33
2053/4165
41/833
19/833
192/54145
1/1
6/4165
1/4165
48899491/164771826258
1/1
2470629/24166534517840
0/1

예제 2
입력
```
2 2 2
a a
0 0 0
```
예상 출력
```
1/3
```
예제 3
입력
```
1 1 1
a
0 0 0
```
예상 출력
```
1/1
```
예제 4
입력
```
3 3 4
a+ * a *
0 0 0
```
예상 출력
```
37/42
```
예제 5
입력
```
2 6 6
a a+ a++ b b+ b++
0 0 0
```
예상 출력
```
4/33
```