2022 软件学院 AK 杯程序设计竞赛

Problem I. Ustinian的围骰

骰宝赌博中,所开出三粒骰仔的点数都是相同,大小通杀:指开围骰,除了买中围骰外其余所有投注都杀。而 Serein 对围骰很感兴趣,连忙跟 Ustinian 分享了这个,了解了围骰规则后,她提出了另一种玩法。

注意题目描述的规则可能与一般的围骰游戏有所区别,请以题目为准。

围骰游戏有 n 个人参与,每人有 56 面骰子。 初始时,每个人随机打乱自己的骰子(摇骰子)。 特别的,围骰之神会在暗中保证:对于每个人的 5 枚打乱后的骰子,不会出现 5 枚骰子的点数从小到大排序后为 (2,3,4,5,6) 的情况。之后每个人仅知道自己的骰子点数。

  • 若当前规则为“斋”,对点数 x(1\le x\le 6),一个玩家的点数 x 的总数目 num_x 为自己的点数为 x 的骰子数目;
  • 若当前规则为“飞”,对点数 x(1\le x\le 6),一个玩家的点数 x 的总数目 num_x 为自己的点数为 x1 的骰子数目。
  • 特别地,若自己的 5 枚骰子点数一样(在“飞”规则下,即只出现 x1 两种),则 num_x 额外加一。

例如,斋时,num_2(1,1,2,2,2)=3,num_2(2,2,2,2,2)=6 ;飞时, num_2(1,2,3,4,5)=2,num_2(1,1,2,2,2)=6,num_2(1,1,1,1,1)=6

定义全场的 x 的数目 tot_x 为各玩家的 num_x 之和。

玩家围成一圈并顺时针叫数,断言在斋或飞下,当前 tot_x 至少是多少。他的下一个玩家如果质疑该断言,则开骰,公开所有人的骰子并统计,若断言正确,下一个玩家负;否则胜。若不质疑,则继续断言。

现给定玩家数 n,上一个玩家断言的规则、x 、总数 tot_x,以及当前自己的骰子情况,请你计算有多大的概率上一个玩家的断言是正确的。

输入

输入一行一个整数 t(1\le t\le10^3),代表询问数。

接下来输入一行四个整数 n,r,x,tot_x(2\le n\le5,1\le r\le 2,1\le x\le 6,0\le tot_x\le 6n)。若 r=1 代表斋,否则代表飞。

接下来输入一行五个整数,第 i 个整数 a_i(1\le a_i\le6) 代表你持有的第 i 个骰子的点数。保证从小到大排序后 a\neq(2,3,4,5,6)

输出

对于每个询问,以 a/b 格式输出一行两个整数 a,b,代表断言正确的概率 \dfrac ab,你需要输出最简分数形式。

样例

标准输入 复制文本
5
2 1 2 6
2 2 2 2 2
3 2 2 6
1 2 1 2 1
2 1 4 4
2 3 3 3 3
3 1 4 10
2 3 3 3 3
5 2 3 9
1 2 3 4 4
标准输出 复制文本
1/1
1/1
13/3828
17/19538112
148076978096/279593130267

提示

对第一、第二个询问,由于自己的 num_2=6,则不管其他人的点数如何,都必然总数不少于 6

对第三个询问,自己 num_4=0,对方 num_4=4 的所有情况 (4,4,4,4,d),d\neq 4,共有 5\times5=25 种;num_4=5 不存在,num_4=6 只有一种情况。总方案数为 6^5-5!=7656\gcd(7656,25+1)=2,故答案为 \dfrac{13}{3828}

对第四个询问,当且仅当一个玩家 num_4=6(只有一种情况)且另一个玩家 num_4=4 时能够凑够 10,情况数为 2\times25\times1=50 种;且不可能凑到 11,凑到 12 只有两个玩家都 num_4=6,仅有一种情况。总方案数为 7656^2\gcd(50+1,7656^2)=3,答案为 \dfrac{17}{7656^2\div 3}

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 12
通过 0

A B C D E F G H I J

比赛结束时将在信205 B进行滚榜,有兴趣的同学可以留下来看
注意D题中的!是阶乘的意思
题目难度总体递增但不保证单调递增,被前面题卡住的可以往后面看看
本次ak杯 16:30 封榜,17:10 比赛结束
由于刚开始服务器问题,本次ak杯延长10min,到17:10结束
第一题,只需要输出三次I Miss Serein