Description

題目背景

冒泡排序的交換次數被定義為交換過程的執行次數。

題面描述
小 S 開始專注于研究?度為 n 的排列，他想知道，在你運氣足夠好的情況下（即每次冒泡排序的交換次數都是可能的最少交換次數，仿佛有上帝之手在操控），對于一個等概率隨機的長度為n 的排列，進行這樣的冒泡排序的期望交換次數是多少？

Input

從文件 inverse.in 中讀入數據。
輸入第一行包含一個正整數 T ，表示數據組數。
對于每組數據，第一行有一個正整數，保證 n ≤ 10^7 。

Output

輸出到文件 inverse.out 中。
輸出共 T 行，每行一個整數。
對于每組數據，輸出一個整數，表示答案對 998244353 取模的結果。

Sample Input

2
2
4

樣例 2
見選手目錄下的 inverse/inverse2.in 與 inverse/inverse2.ans 。

Sample Output

499122177
415935149

Data Constraint

Solution

• 這題的方法非常多，各路大佬各顯神通……

• 我還是從最簡單的講起吧：

方法①：

• 一個排列要變成 $1$ 到 $n$，交換的方法肯定是沿著環來互換。

• 一個大小為 $k$ 的環，就需要 $k?1$ 步交換來達到有序。

• 顯然環越多所需的交換次數越少，若有 $p$ 個環，則答案為 $n?p$ 。

• 于是設 $f[i]$ 表示這 $i$ 個點形成環的期望個數。

• 則有轉移：$$f[i]=f[i?1]+\frac{1}{i}$$

• （第 $i$ 個點可能自成一環，也可能被安排進前 $i?1$ 的那些環內）

• 于是我們 $O(n)$ 預處理出 $f[i]$ ，每讀入一個 $n$ 輸出 $n?f[n]$ 即可。

• 注意求 $1$ 到 $n$ 的倒數不要每次快速冪，會超時，應該 $O(n)$ 線性求。

• 不會的話可以看看這里：O(N) 求 1~N 逆元 模板及證明

• 于是我們就 $O(n)$ 解決本題啦！

方法②：

• 現在來講 pty 提供的解法！

• 仍然考慮環的貢獻，枚舉環的大小 $i$ ，單獨算貢獻，則答案即為： $$\sum _{i=2}^n{C}_n^i?(i?1)!?(n?i)!?(i?1)$$

• 其中 $C_n^i$ 表示從 $n$ 中選 $i$ 個點形成環，$(i?1)!$ 表示這 $i$ 個點隨便排（注意不是 $i!$ ，環的方向可以變），$(n?i)!$ 表示剩下 $n?i$ 個點隨便排，$(i?1)$ 表示大小為 $i$ 的環需要交換 $(i?1)$ 次。

• 那么上式可化為：$$\sum _{i=2}^n\frac{i?1}{i}$$

• 即：$n?f[n]$ ，兩種方法算出來的結果是一樣的！

方法③：

• 當然還有一些對數字十分敏感的同學都能找到規律了。

• 設答案中分子為 $a_n$ ，則分母為 $n!$ ，可以發現關于 $a_n$ 的遞推式：$$a_n=n{a}_{n?1}+(n?1)(n?1)!$$

• 發現方法玄學，這里不再展開，有興趣的同學可以課下研究……

Code

#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int N=1e7+5,mo=998244353; int f[N]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } int main() {freopen("inverse.in","r",stdin);freopen("inverse.out","w",stdout);f[0]=f[1]=1;for(int i=2;i<N;i++) f[i]=(LL)(mo-mo/i)*f[mo%i]%mo;for(int i=2;i<N;i++) f[i]=(f[i]+f[i-1])%mo;int T=read();while(T--){int n=read();write((n-f[n]+mo)%mo),putchar('\n');}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5931. 【NOIP2018模拟10.27】冒泡排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。