【补题】牛客练习赛105-B

2022-11-05 14:10 作者:羽走 0人读过 | 我要投稿

赛时写这道题的时候，推了一个小时还是失败了，看来是自己的高中数学知识太弱了，死去的知识突然攻击我。

那么战胜恐惧的办法只有直面恐惧。

[立正与挨打]

读完题目还觉得是期望概率题差点就跑路了

在赛时，犯了一个极大的惯性思维的错误，就是认为一个数和它自身的最大公约数是1，导致样例看了半天还没看懂，于是又想了一下，发现一个数和它自身的最大公约数就是他自己，于是发现了这个题只要存在偶数在偶数位或者第一位上就行。于是后面的排列组合就算不对了......

于是赛后去补题，发现自己的思路和题解差别还是挺大的。

首先考虑逆向思维，既然题目要我们找偶数位置上的方案数，那么我们就找逆向的答案，找偶数在奇数位上的方案数，最后用 $n%0A$ $-$ 逆向答案。
先考虑 $n$ 为奇数时，共有 $%5Cfrac%7Bn%2B1%7D%7B2%7D%20$ 个位置可以放 $%5Cfrac%7Bn-1%7D%7B2%7D%20$ 个偶数和 $%5Cfrac%7Bn%2B1%7D%7B2%7D%20$ 个奇数，我们先从这 $%5Cfrac%7Bn%2B1%7D%7B2%7D%20$ 个奇数中挑出一个奇数，剩下奇数位置和偶数位置分别全排列就可以了，最终当 $n$ 为奇数时候逆向方案数为 $C_%7B%5Cfrac%7Bn%2B1%7D%7B2%7D%7D%5E1$ $(%5Cfrac%7Bn-1%7D%7B2%7D)!%20$ $(%5Cfrac%7Bn%2B1%7D%7B2%7D%20)%EF%BC%81$ $%3D((%5Cfrac%7Bn%2B1%7D%7B2%7D%20)!)%5E2%20$
然后考虑 $n%0A$ 为偶数，当 $n$ 为偶数的时候就比较简单了，直接奇数位置和偶数位置都来一遍全排列就好，仍然是把偶数放到奇数位置上 $(%5Cfrac%7Bn%7D%7B2%7D%20)!(%5Cfrac%7Bn%7D%7B2%7D)!%20%3D%20((%5Cfrac%7Bn%7D%7B2%7D)!)%5E2%20$
所以，不符合题目条件的方案数总共有 $(%5Clfloor%20%5Cfrac%7Bn%2B1%7D%7B2%7D%20%20%5Crfloor!%20%20)$ ，然后用总的方案数 $n!$ 减去不符合的方案数就可以得到答案了。