sigman

一位來自邵陽XJ的初三菜雞Oier

博客園
首頁
新隨筆
聯(lián)系
管理

一道題目

Posted on 2025-04-25 18:21 K_J_M 閱讀(29) 評論(0) 收藏舉報

一道題目

給定正整數(shù) $n \le 1000$，求出不滿足下面任意條件的排列的個數(shù)：

$p_i=i$
$p_i=j,p_j=k,p_k=i$

其中 $i,j,k \in [1,n]$ 且互異。

Solution

講下面兩個方法時首先聲明定義：

$\text{n-循環(huán)}$ 是指一個 $1\sim n$ 的排列在經(jīng)過任意排列轉(zhuǎn)化之后得到的排列。

容斥

首先上面的條件就等價于排列中沒有 $\text{1-循環(huán)}$ 和 $\text{3-循環(huán)}$ 的個數(shù)，也可以等于錯排的數(shù)量減去至少含有一個 $\text{3-循環(huán)}$ 的錯排個數(shù)。首先錯排的數(shù)量記為 $g_n$，則 $g_n=(n-1)\times(g_{n-1}+g_{n-2})$。現(xiàn)在要去掉至少一個 $\text{3-循環(huán)}$ 的錯排，考慮選出三個數(shù) $n \choose {3} $ 種選法，然后有效的排列只有兩個，現(xiàn)在我們已經(jīng)固定了一個 $\text{3-循環(huán)}$，然后其他的 $n-3$ 個數(shù)可以構(gòu)成 $g_{n-3}$ 個排列。但是這 $g_{n-3}$ 種中也包含了一些 $\text{3-循環(huán)}$，我們在選擇一個 $\text{3-循環(huán)}$ 時，$g_{n-3}$ 個排列中也會有 $\text{3-循環(huán)}$，我們下次在計算另一個 $\text{3-循環(huán)}$ 時會重復，所以我們需要通過容斥去掉重復。第一次選擇一個 $\text{3-循環(huán)}$ 時，至少有兩個 $\text{3-循環(huán)}$ 的會多減一次，下次我們就需要加上。總的來說我們的式子為

\[g_n+\sum_{i=1}^{\lfloor \frac{n}{3} \rfloor}(-1)^i\frac{n!}{i!\times 3^i\times (n-3i)!}\times g_{n-3i} \]

時間復雜度 $\mathcal O(n)$。

組合

按照排列中沒有 $\text{1-循環(huán)}$ 和 $\text{3-循環(huán)}$ 的個數(shù)的思路去亂搞。

首先我們需要求出只有 $\text{n-循環(huán)}$ 的排列個數(shù)，設(shè) $n$ 排列的 $\text{n-循環(huán)}$ 個數(shù)為 $h_n$。我們發(fā)現(xiàn) $1$ 位置上只能填 $2\sim n$ 中的一個，共 $n-1$ 種，設(shè)填 $x$，則 $x$ 位置上只能填除了 $x,1$ 的其他數(shù)，因為為了保證只有 $\text{n-循環(huán)}$，而 $x$ 位置上填 $1$ 就會出現(xiàn) $\text{2-循環(huán)}$。這樣一直推下去就會發(fā)現(xiàn) $h_n=(n-1)!$。

有了這個基礎(chǔ)后我們就夠推出式子了。

設(shè)答案為$a_n$，假設(shè)當前我們考慮到第 $n$ 項，那么這一項只能位于 $2,4,5\dots$ 循環(huán)，當位于 $k$ 循環(huán)時，我們可以從前面 $n-1$ 個數(shù)中選出 $k-1$ 個數(shù)，然后這 $k-1$ 個數(shù)和 $n$ 構(gòu)成 $k$ 個數(shù)，然后構(gòu)成的只是 $\text{k-循環(huán)}$ 的有 $(k-1)!$ 種方法，最后還有剩下的 $n-k$ 個數(shù)的答案 $a_{n-k}$。將每一種情況進行求和可以得到

\[a_n=(n-1)a_{n-2}+\sum_{k=4}^{n}{n-1 \choose k-1}\times (k-1)! \times a_{n-k} \]

但是這樣做的時間復雜度為 $\mathcal O(n^2)$，我們顯然還可以做到更優(yōu)。

將上面的式子化一下簡可以得到

\[a_n=(n-1)a_{n-2}+(n-1)!\sum_{i=0}^{n-4}\frac{a_i}{i!} \]

寫出 $a_{n-1}$

\[a_{n-1}=(n-2)a_{n-3}+(n-2)!\sum_{i=0}^{n-5}\frac{a_i}{i!} \]

發(fā)現(xiàn)

\[(n-1)!\sum_{i=0}^{n-4}\frac{a_i}{i!}=(n-1)\times \{(n-2)!\sum_{i=0}^{n-5}\frac{a_i}{i!}\}+(n-1)!\times \frac{a_{n-4}}{(n-4)!} \]

所以

\[a_n=(n-1)\times [a_{n-1}-(n-2)a_{n-3}]+(n-1)!\times \frac{a_{n-4}}{(n-4)!} \]

化簡一下可以得到

\[a_n=(n-1)(a_{n-1}+a_{n-2}-(n-2)a_{n-3}+(n-2)(n-3)a_{n-4}) \]

這樣我們的時間復雜度就做到了 $\mathcal O(n)$。

后續(xù)

此題是蒟蒻校模擬賽的 T2，蒟蒻當時只寫了 $n\le 12$ 的暴力分。賽后想推一下式子，但是無果。于是乎蒟蒻便將此題給本校數(shù)學超強的 fsy 解答，也無果，于是又給本校的數(shù)學競賽班老師 zyz 進行解答，也無果，于是只好蒟蒻自己推式子了。推了很久終于推出來 $n^2$ 式子，進行驗證發(fā)現(xiàn)非常正確，于是報告教練。但教練用容斥推出上面的 $\mathcal O(n)$ 式子，蒟蒻于是重新對式子進行思考，發(fā)現(xiàn)可以數(shù)學做到 $\mathcal O(n)$，最后就有了這兩種不同方法。但我們還對該題進行發(fā)帖，發(fā)現(xiàn)網(wǎng)上大神 10min 就用一種我們看不懂的方法迅速而又正確的解答了這個問題，瞠目結(jié)舌。于是這道題目經(jīng)過兩周的思考，最終思想薈萃。

刷新頁面返回頂部