#1775. 麻将

    ID: 1775 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest137来源:qoj.ac数据:公开样例枚举

麻将

麻将

题目描述

标题: 麻将 - Problem - QOJ.ac

#3686. 麻将

Statistics

The problem was used in the following contests:

问题描述

麻将是个风靡亚洲的游戏。麻将有下面这样的牌,每种牌最多4张:

problem_3686_1.png 我们分别用1m,2m,3m,…,9m来表示这些牌。

problem_3686_2.png 我们分别用1s,2s,3s,…,9s来表示这些牌。

problem_3686_3.png 我们分别用1p,2p,3p,..,9p来表示这些牌。

problem_3686_4.png 我们分别用1c,2c,3c,…,7c来表示这些字牌。

一个一般的胜利状态是指一个 14 张牌的集合,包含一对相同的牌(例:2s,2s 或 4c,4c),和四组牌,每组牌包含 3 张牌,要么是 3 张相同的牌(例:6m,6m,6m 或 2c,2c,2c),要么是三张连续的同种类的非字牌(例:4m,5m,6m 或 1p,2p,3p)。

还有两种特殊的胜利状态。第一种是“七对子”,即7个组,每组为一对相同的牌,不同组的牌不能相同(例:1m,1m,2m,2m,4m,4m,5m,5m,6c,6c,1s,1s 是一个可行的方案,而 1m,1m,2m,2m,4m,4m,5m,5m,2m,2m,1s,1s 则不是,因为有一组牌相同了)。

第二种是“国士无双”,指 1m,9m,1s,9s,1p,9p,1c,2c,3c,4c,5c,6c,7c 各一张,再加上一张任意的之前提到的 13 张牌中的一张(例:1m,9m,1s,9s,1p,9p,1c,2c,3c,4c,5c,6c,7c,9p)即为一个胜利状态。

现在,已知有 N 张牌,每种牌的数量不会超过 4 张,求天和(即拿 14 张牌,这 14 张牌恰好是胜利状态)的概率。

输入格式

多组数据。对于每个测试点,第一行有一个数 T,表示共 T 组数据。对于每组数据,第一行一个数 N,接下来一行包含 N 个字符串,表示 N 张牌。具体参见样例。

输出格式

对于每组数据,输出一行,以最简分数形式表示所求的天和的概率。分子分母间用字母’/’分割(不含引号)。

样例输入

4
14
1s 2s 3s 2c 2c 2c 2p 3p 4p 5m 6m 7m 1p 1p
14
1s 2s 3s 2c 2c 2c 2p 3p 4p 5m 6m 7m 1p 2p
25
1m 1m 9m 9m 1s 1s 9s 9s 1p 1p 9p 9p 1c 1c 2c 2c 3c 3c 4c 4c 5c 5c 6c 6c 7c
27
1m 1m 1m 2m 2m 2m 3m 3m 3m 4m 4m 4m 5m 5m 5m 6m 6m 6m 7m 7m 7m 8m 8m 8m 9m 9m 9m

样例输出

1/1
0/1
1057/185725
44171/371450

数据规模和约定

对于 40% 的数据,N≤25。

对于 100% 的数据,数据组数 T 不超过 10 组,14≤N≤136。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4
14
1s 2s 3s 2c 2c 2c 2p 3p 4p 5m 6m 7m 1p 1p
14
1s 2s 3s 2c 2c 2c 2p 3p 4p 5m 6m 7m 1p 2p
25
1m 1m 9m 9m 1s 1s 9s 9s 1p 1p 9p 9p 1c 1c 2c 2c 3c 3c 4c 4c 5c 5c 6c 6c 7c
27
1m 1m 1m 2m 2m 2m 3m 3m 3m 4m 4m 4m 5m 5m 5m 6m 6m 6m 7m 7m 7m 8m 8m 8m 9m 9m 9m
1/1
0/1
1057/185725
44171/371450