题目链接
题意
大神给定一个正整数n,要求我们随机的在纸上写出整数集合${1,2,3,…,3\times
n+1}$(n为正整数)的一个排列,要求在谢的过程中从第一个数到正在写的数的和不是3的倍数,如果能写出符合要求的一个排列则游戏获胜,请问赢得游戏的概率。
输入
开始输入一个正整数t表示测试样例的个数
接下来t行每行一个正整数n,表示一个样例
$1\leq n\leq 15$
输出
对于每个样例,输出获胜的概率(结果保留9位有效数字)
Sample Input
1 | 1 |
Sample Output
1 | 1 |
分析
对于分母而言,由于是$[ 1,3\times n+1 ]$的全排列,则需要计算$(3\times n+1)!$而$n=15$那么分母要么用大数,要么推公式,接下来我们推导公式
对于分子而言,分子等于符合要求的排列的数量,接下来我们分析这种排列的数量。
对于$[ 1,3\times n+1 ]$,由于我们考虑的是它们的和是否是3的倍数,那么我们对这些数都取模3,则数列变为:
$1,2,3,1,2,3,…,1$
接下来我们考虑1,2,3的个数分别为多少:
1:每三个数中有一个,再加最后一个,则为$n+1$个
2:每三个数中有一个,即$n$个
3:每三个数中有一个,即$n$个
那么这些数3无法放在第一位,而3放在某个数之后时,在模3的情况下,之前的数的和不会改变,那么我们可以先把3全部拿出来不暂时不讨论
那么这些数总共还剩$2\times n+1$个,再讨论首位为2的情况,由于首位为2,那么第二位不能是1,则第二位也为2,即:
$2,2$
那么他们的和在模3的情况下为1,那么第三位不能是2,则第三位为1,即
$2,2,1$
他们的和为2(mod 3),那么第四位不能是1,则第四位为2,即
$2,2,1,2$
他们的和为1,则出现循环,即之后的数的排列为1,2交替出现,但是2的个数比1的个数少一个,那么之后必定会出现两个连续的1,即$2,1,1$,当结尾为2时,和为1(mod 3),在加两个连续的1,那么结果将会是3的倍数,所以首位不能为2。
于是首位只能是1,同理,首位为1的情况下,排列为:
$1,1,2,1,2,1,2….$,即第一位第二位为两个1,之后1,2交替。
由于1的数量刚好比2多一个,则除首位1以外,1,2刚好两两匹配,符合题意。
那么考虑了这个排列的个数,第一位为$n+1$个1中选一个$C_{n+1}^1$,第二位为$n$个1中选一个$C_n^1$,第三位为$n$个2中选一个$C_n^1$以此类推,则总共有$(n+1)!\times n!$种。
由于将3放在某个排列的末尾,在模3的情况下,不会改变该排列的和,则将3插入到这个排列的任意排列之后即可,由于3无法插入到首位,那么插入第一个3时有$2\times
n+1$种插法,插入第二个3时,由于之前插入了一个3,则排列多了一个数,则有$2\times n+2$种,以此类推,插入最后一个3时有$3\times n$种方法。
所以综上所述,总共有$(n+1)!\times n!\times (2\times n+1)\times (2\times n+2)\times …\times (3\times n)$种。
于是概率为$\frac {(n+1)!\times n!\times (2\times n+1)\times (2\times n+2)\times …\times (3\times
n)}{(3\times n+1)!}$,上下同时约去$(n+1)!$,为:
$\frac {n!\times (2\times n+1)\times (2\times n+2)\times …\times (3\times n)}{(n+2)\times …\times
(3\times n+1)}$
在上下同时除以$(2\times n+1)\times (2\times n+2)\times …\times (3\times n)$,为:
$\frac {n!}{(n+2)\times (n+3)\times …\times (2\times n)\times (3\times n+1)}$。
在上下同时乘以$(n+1)$得:
$\frac {n!\times (n+1)}{(n+1)\times (n+2)\times … \times (2\times n)\times (3\times
n+1)}$,即$\frac {n+1}{3\times n+1}\times \frac {n!}{(n+1)\times (n+2)\times …\times (2\times
n)}$,于是后一项就可以以O(n)的方法算出,且不会超过范围。
AC代码
查看代码
1 |
|