【考前冲刺Day1】黑红树

题面

题解转自zhber的这篇文章,本人对部分公式做了LaTex处理,如需转载请注明原作者

zhb原创出品,改编自高一暑假数学作业必修三那章最后一题

这是这套题唯一会比较防ak的题了

首先题目我写了一大堆,就是要把你搞晕的

题意是有两个人进行游戏,其中第一个人在每局中获胜的概率是\(\frac{p}{q}\),如果有一个人比另一个人多赢两局,则游戏结束。现在给出T个询问,每个询问Q表示求游戏刚好在第Q轮结束的精确概率\(\frac{a}{b}\)的a%k和b%k。要求\(\frac{a}{b}\)是这个概率的最简分数。

解法是这样的:

我们把每两局压成一轮,只有三种可能:第一个人赢了,第二个人赢了,两人各赢一局。这样如果有人赢了游戏结束,平局时两人分数相同,相当于又开始一局

这样我们注意到一个显然的事实:游戏不可能在奇数局结束。因为由上面的推论+自己yy可知,要结束一定是在一轮以后,就是偶数局之后。这样不合法情况删掉一半了

第一个人一轮赢必须连赢两局,就是\((\frac{p}{q})^2\),即\(\frac{p^2}{q^2}\)

第二个人一轮赢也是连赢两局,就是\((1-p/q)^2\),通分完\(\frac{(p-q)^2}{q^2}\)
那么一局能结束的概率就是上面两个加起来,即\(\frac{p^2+(p-q)^2}{q^2}\)

一局不能结束的概率就是1-"上面那式子"

为简化条件,我们令一轮能结束的概率是A/B,一轮不能结束的概率是C/D。计算方法见上

那么对于有意义的询问,即偶数Q,令t=Q/2

那么比赛在第t轮即第Q局结束的充要条件是:在1到t-1轮两人都是平局,并且在第t轮比赛刚好结束

那么对于询问Q,\((\frac{C}{D})^{t-1} \times \frac{A}{B}\) 即是所求

到这里应该都还能理解吧

然后比较难搞的是取模。因为p、q是100级别,那么\(p^2\)、\(q^2\)是1w级别,就是说ABCD这些数都是10000级别

要求的分数分子是\(C^{t-1}\times A\),分母是\(D^{t-1}\times B\),还要进行约分完取模。我们可以直接预处理使得A和B、C和D分别互质,但是我们没法保证A和D、B和C分别互质。这样约分就有困难了。比如A分解质因数有2^十几次方吧,D只有2^1,那么在接下来的十几次操作中都要用D的2去约掉A的2。但是ABCD的数据规模还算小,所以我们暴力搞出前20轮的答案,然后这样一来改约的也就约干净了,然后每次分子只乘C分母只乘D,又没有约分,可以直接递推。

代码

点赞
  1. Lxp_Mike说道:
    Google Chrome Windows 10

    我才是最强的!!! 哈哈哈哈!!

  2. Nietsne说道:
    Google Chrome Windows 10

    望早日 AC (我想引用

发表评论

电子邮件地址不会被公开。必填项已用 * 标注