#HTR001B. 抽奖

抽奖

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

蒙提霍尔问题(Monty Hall problem\text{Monty Hall problem}),又称三门问题,最初来源于美国的一档电视游戏类节目——Let’s Make a Deal\text{Let’s Make a Deal},因其主持人为 Monty Hall\text{Monty Hall} 而得名。问题可以描述如下:在电视游戏节目中,主持人设置了三道门,分别为 11 号、22 号、33 号,其中一扇门后面有一辆小轿车作为奖品,另外两扇门后各为一只山羊。竞猜者可以随机挑选一扇门,比如,选择 11 号门,之后主持人在 22 号门和 33 号门中选择一扇藏有山羊的门打开,比如说 33 号门,然后让你作出选择:你是否愿意放弃选择 11 号门转而选择 22 号门?

更换门的选择能够使得中奖率更高吗?

从直觉来看,有两种主要的意见:第一种意见认为剩下的两扇门必定一扇门是山羊,另外一扇门是小轿车,换选后中奖概率是 12\dfrac{1}{2},而不换选的中奖概率是 13\dfrac{1}{3};第二种意见认为只剩下一扇尚未选择的门,而门后面有小轿车的概率同样是 13\dfrac{1}{3},所以换选和不换选的中奖概率不变。但是通过谨慎的理论分析和计算机数据模拟都可以得出以下正确的结论:不换选的中奖概率为 13\dfrac{1}{3},换选的中奖概率为 23\dfrac{2}{3}。这个结论非常反直觉,使得当时的很多读者(其中 110\dfrac{1}{10} 的人具有博士学位)写信给刊登这个结论的杂志,表示他(她)们拒绝相信“换选具有 23\dfrac{2}{3} 的中奖概率”是正确的结论。

实际上转换一下思维方式就很容易理解这个问题,从而明白正确结论就是换选门具有更高的中奖概率。假设竞猜者选择的是 11 号门,则有以下可能性:

11 号门 22 号门 33 号门 不换选 换选
小轿车 山羊 山羊 小轿车 山羊
山羊 小轿车 山羊 小轿车
山羊 小轿车

容易看出,不换选中奖的概率为 13\dfrac{1}{3},换选后中奖概率为 23\dfrac{2}{3}。如果竞猜者初始选择 22 号门或者 33 号门具有同样的结果。

题目描述

现在我们来研究蒙提霍尔问题的一个扩展。某位竞猜者参加蒙提霍尔主持的抽奖节目,主持人设置了 nn 扇门,并在 aa 扇门后设有奖品,剩余的 nan - a 扇门后未设置奖品。当竞猜者随机选中一扇门后,主持人打开另外 bb 扇门,打开的 bb 扇门中有 cc 扇门后有奖品,此时主持人询问竞猜者是否将当前选中的门换成另外一扇尚未打开的门。由于竞猜者对概率论一窍不通,无法确定换选门后的中奖概率究竟是多少,因此竞猜者将这个问题交给你来处理。

不难证明,可以将换选门后的中奖概率表示为一个最简分数 pq\dfrac{p}{q},其中 ppqq 互质。试确定一个最小的自然数 xx,使得 pqx(modP)p \equiv qx \pmod P,其中 P=998244353P=998244353,可以证明这样的自然数 xx 必定存在。

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 TT,表示测试数据的组数。接下来每行包含一组测试数据,一组测试数据包含四个整数:nnaabbcc

输出格式

对于每组测试数据输出一行,包含一个符合题意要求的自然数 xx

输入输出样例

2
3 1 1 0
10 3 6 2
665496236
33274812

说明/提示

样例说明

对于样例 #1 中的第一组数据,共有 33 扇门,在 11 扇门后设有奖品,竞猜者选中一扇门后,主持人打开另外 11 扇门,另外打开的 11 扇门中有 00 扇门包含奖品,此种情形在题目背景中已经说明,换选门后的中奖概率为 23\dfrac{2}{3},故 p=2p=2q=3q=3,则 x=665496236x=665496236


数据规模

  • 对于 10%10\% 的数据,3n103 \le n \le 10
  • 对于 30%30\% 的数据,3n1033 \le n \le 10^3
  • 对于 100%100\% 的数据,3n1053 \le n \le 10^5

对于 100%100\% 的数据,1T1001 \le T \le 1001an11 \le a \le n-11bn21 \le b \le n-20c<min(a, b)0 \le c \lt \operatorname{min}(a, \ b)

2021 CoE 挑战编程 III (Hydro Tritium Round #001)

未参加
状态
已结束
规则
IOI
题目
6
开始于
2021-7-3 14:00
结束于
2021-7-3 18:00
持续时间
4 小时
主持人
参赛人数
73