Description

題目背景

冒泡排序的交換次數(shù)被定義為交換過程的執(zhí)行次數(shù)。

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

Input

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

Output

輸出到文件 inverse.out 中。
輸出共 T 行，每行一個(gè)整數(shù)。
對于每組數(shù)據(jù)，輸出一個(gè)整數(shù)，表示答案對 998244353 取模的結(jié)果。

Sample Input

2
2
4

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

Sample Output

499122177
415935149

Data Constraint

Solution

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

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

方法①：

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

• 一個(gè)大小為 $k$ 的環(huán)，就需要 $k?1$ 步交換來達(dá)到有序。

• 顯然環(huán)越多所需的交換次數(shù)越少，若有 $p$ 個(gè)環(huán)，則答案為 $n?p$ 。

• 于是設(shè) $f[i]$ 表示這 $i$ 個(gè)點(diǎn)形成環(huán)的期望個(gè)數(shù)。

• 則有轉(zhuǎn)移：$$f[i]=f[i?1]+\frac{1}{i}$$

• （第 $i$ 個(gè)點(diǎn)可能自成一環(huán)，也可能被安排進(jìn)前 $i?1$ 的那些環(huán)內(nèi)）

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

• 注意求 $1$ 到 $n$ 的倒數(shù)不要每次快速冪，會(huì)超時(shí)，應(yīng)該 $O(n)$ 線性求。

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

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

方法②：

• 現(xiàn)在來講 pty 提供的解法！

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

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

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

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

方法③：

• 當(dāng)然還有一些對數(shù)字十分敏感的同學(xué)都能找到規(guī)律了。

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

• 發(fā)現(xiàn)方法玄學(xué)，這里不再展開，有興趣的同學(xué)可以課下研究……

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位技術(shù)專家面對面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。