2017南华大学省赛选拔赛,A大神的游戏

题目链接

2017南华大学省赛选拔赛——A 大神的游戏(内网访问)

题意

大神给定一个正整数n，要求我们随机的在纸上写出整数集合 $\{1,2,3,…,3\times n+1\}$ (n为正整数)的一个排列，要求在谢的过程中从第一个数到正在写的数的和不是3的倍数，如果能写出符合要求的一个排列则游戏获胜，请问赢得游戏的概率。

输入

开始输入一个正整数t表示测试样例的个数

接下来t行每行一个正整数n，表示一个样例

$1\leq n\leq 15$

输出

对于每个样例，输出获胜的概率(结果保留9位有效数字)

Sample Input

Sample Output

1
2
3

1

0.250000000

分析

对于分母而言，由于是 $[ 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代码

查看代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
    int t;
    while(t--){
        int n;
        cin>>n;
        double ans = (n + 1.0) / (3 * n + 1);
        for(int i = 1; i <= n; i++){
            ans *= (i * 1.0) / (n + i);
        }
        printf("%.9lf\n", ans);
    }
    return 0;
}