【補(bǔ)題】?？途毩?xí)賽105-B

2022-11-05 14:10 作者:羽走 0人讀過(guò) | 我要投稿

????? ?

?????????賽時(shí)寫(xiě)這道題的時(shí)候，推了一個(gè)小時(shí)還是失敗了，看來(lái)是自己的高中數(shù)學(xué)知識(shí)太弱了，死去的知識(shí)突然攻擊我。

????????那么戰(zhàn)勝恐懼的辦法只有直面恐懼。

[立正與挨打]

題目來(lái)源于牛客練習(xí)賽105：https://ac.nowcoder.com/acm/contest/44749/B

讀完題目還覺(jué)得是期望概率題差點(diǎn)就跑路了??

在賽時(shí)，犯了一個(gè)極大的慣性思維的錯(cuò)誤，就是認(rèn)為一個(gè)數(shù)和它自身的最大公約數(shù)是1，導(dǎo)致樣例看了半天還沒(méi)看懂，于是又想了一下，發(fā)現(xiàn)一個(gè)數(shù)和它自身的最大公約數(shù)就是他自己，于是發(fā)現(xiàn)了這個(gè)題只要存在偶數(shù)在偶數(shù)位或者第一位上就行。于是后面的排列組合就算不對(duì)了......

于是賽后去補(bǔ)題，發(fā)現(xiàn)自己的思路和題解差別還是挺大的。

首先考慮逆向思維，既然題目要我們找偶數(shù)位置上的方案數(shù)，那么我們就找逆向的答案，找偶數(shù)在奇數(shù)位上的方案數(shù)，最后用 $n%0A$ $-$ ?逆向答案。
先考慮? $n$ ?為奇數(shù)時(shí)，共有? $%5Cfrac%7Bn%2B1%7D%7B2%7D%20$ ? 個(gè)位置可以放? $%5Cfrac%7Bn-1%7D%7B2%7D%20$ ?個(gè)偶數(shù)和? $%5Cfrac%7Bn%2B1%7D%7B2%7D%20$ ?個(gè)奇數(shù)，我們先從這? $%5Cfrac%7Bn%2B1%7D%7B2%7D%20$ ?個(gè)奇數(shù)中挑出一個(gè)奇數(shù)，剩下奇數(shù)位置和偶數(shù)位置分別全排列就可以了，最終當(dāng)? $n$ ?為奇數(shù)時(shí)候逆向方案數(shù)為? $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$ ?為偶數(shù)，當(dāng)? $n$ ?為偶數(shù)的時(shí)候就比較簡(jiǎn)單了，直接奇數(shù)位置和偶數(shù)位置都來(lái)一遍全排列就好，仍然是把偶數(shù)放到奇數(shù)位置上 $(%5Cfrac%7Bn%7D%7B2%7D%20)!(%5Cfrac%7Bn%7D%7B2%7D)!%20%3D%20((%5Cfrac%7Bn%7D%7B2%7D)!)%5E2%20$
?所以，不符合題目條件的方案數(shù)總共有 $(%5Clfloor%20%5Cfrac%7Bn%2B1%7D%7B2%7D%20%20%5Crfloor!%20%20)$ ，然后用總的方案數(shù)? $n!$ ?減去不符合的方案數(shù)就可以得到答案了。