娱乐 每 期 算 法 挑 战 #1

[Mr.K 018]

应 @摸鱼奇才咖啡喵 的邀请，我回来接着班门弄斧辣！

什么叫每期算法挑战呢？就是说，算法挑战每更一期，算法挑战就更一期

第一期，先来一个简单题吧。

#1 题目来自哥们的×家凤1800

描述

MrK 019是一名大一新生。这一天他随机翻开刚买的×家凤1800，映入眼帘的就是这道题：

有编号为1,2,3的三本书。现随机排列之，求至少有一本书编号与位置相同的概率。

019心说这还不简单，直接暴力枚举出了结果2/3。但万万没想到，此时018从旁边走过，大笔一挥把题干中的3改成了500……

输入

第一行一个整数m（1≤m≤1000），表示样例个数；
接下来m行，每一行都是对应样例中书的数量n（1≤n≤500）。

输出

输出m行，每行一个小数，表示对应样例所求概率，保留8位有效数字。

样例输入

2
3
4

样例输出

0.66666667
0.62500000

样例输出的解释：

2个样例，对于样例1，三本书可能的排法有6种，其中合题意的排法有123、132、213、321四种，因此概率为2/3；

对于样例2，四本书可能的排法有24种，其中合题意的有1234、1243、1324、1342、1423、1432、2134、2314、2431、3124、3214、3241、4132、4213、4231共15种，因此概率为15/24，即5/8。

三月 3, 2021，由Mr.K 018修改
增加样例解释

[EX0w0]

15 小时前, Mr.K 018 说道:

什么叫每期算法挑战呢？就是说，算法挑战每更一期，算法挑战就更一期

w这句话总感觉会报错（x

[苍云静岳]

18 小时前, Mr.K 018 说道:

什么叫每期算法挑战呢？就是说，算法挑战每更一期，算法挑战就更一期

溢出了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

 

顺便样例输出是不是少了一行0.50000000

[Mr.K 018]

11 分钟前, 苍云静岳 说道:

溢出了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊

 

顺便样例输出是不是少了一行0.50000000

ん？（察觉）

样例输出没少，输入的第一行是说会有两个样例

要不我写一下样例输出的解释吧

三月 3, 2021，由Mr.K 018修改

[抹消思绪]

1减全乱排除以全排列咯。全乱排表达式好推，但这种大整数的题我一直不太会，先插个眼吧。

[Mr.K 018]

55 分钟前, 抹消思绪 说道:

1减全乱排除以全排列咯。全乱排表达式好推，但这种大整数的题我一直不太会，先插个眼吧。

这个题的数据量我是考虑过的，可以不涉及大整数运算（还是天杀的乘除运算），误差（应该）也不会超过1e-8的限度。

当然实际上还有另外的问题，这个问题说出来基本上就是透露正确答案了，当然不影响解答。我看你应该是有思路了，不妨说一说？（也方便我们发糖

 

顺带一提，复杂度可以降到O(m+n)

三月 4, 2021，由Mr.K 018修改

[抹消思绪]

9 小时前, Mr.K 018 说道:

这个题的数据量我是考虑过的，可以不涉及大整数运算（还是天杀的乘除运算），误差（应该）也不会超过1e-8的限度。

当然实际上还有另外的问题，这个问题说出来基本上就是透露正确答案了，当然不影响解答。我看你应该是有思路了，不妨说一说？（也方便我们发糖

 

顺带一提，复杂度可以降到O(m+n)

O(m+n)是怎么回事，n不是每个样例不一样么，整个问题里有m个不同的n才对。

 

（顺带一提，x家凤的习题集我觉得好烂……

[Mr.K 018]

1 小时前, 抹消思绪 说道:

O(m+n)是怎么回事，n不是每个样例不一样么，整个问题里有m个不同的n才对。

 

（顺带一提，x家凤的习题集我觉得好烂……

公式推出来就能发现了。

(×家凤的我觉得还行，全做一遍弄会之后，考试基本上就都能做了。反正我看有人先刷1800后做真题，真题做完直呼就这？反倒是李永乐的边学边做做完一遍之后没什么收获

[抹消思绪]

3 小时前, Mr.K 018 说道:

公式推出来就能发现了。

(×家凤的我觉得还行，全做一遍弄会之后，考试基本上就都能做了。反正我看有人先刷1800后做真题，真题做完直呼就这？反倒是李永乐的边学边做做完一遍之后没什么收获

菜逼直接Google了，那确实依次算右边括号里的和式就完了，一直算到最大的n。

（一战做的x宇，二战买了x家凤感觉题有的太无聊有的太怪，又扔了做x宇去了。

[Mr.K 018]

1 小时前, 抹消思绪 说道:

菜逼直接Google了，那确实依次算右边括号里的和式就完了，一直算到最大的n。

（一战做的x宇，二战买了x家凤感觉题有的太无聊有的太怪，又扔了做x宇去了。

对就是这个公式。

公式其实不难推，本质上就是套那个多个事件并的概率的那个公式就可以了

[smallblood]

我的天  原来还有学习的内容！

[Mr.K 018]

12 小时前, smallblood 说道:

我的天  原来还有学习的内容！

学习谈不上，图一乐罢了

真学习谁来sstm啊

[魔冰神]

我还以为是机器学习的算法

[xxxmie]

看到算法想试试，一看概率蒙蔽了- -

[yyh]

这个问题是一个典型的错位排列问题。在许多关于组合数学的书中都有提到。

于 2021/3/5 于 PM1点21分, 抹消思绪 说道:

菜逼直接Google了，那确实依次算右边括号里的和式就完了，一直算到最大的n。

（一战做的x宇，二战买了x家凤感觉题有的太无聊有的太怪，又扔了做x宇去了。

这个式子虽然看起来简单，但是阶乘算起来却很费时间，而且编程的话很容易爆int。

其实按照组合推理的方法可以推出它的递推公式是：

由题目条件不难看出初始条件为D1=0。

用这个公式迭代计算的话，计算量小很多。

没想到在sstm还能看到这样的问题