117 lines
1.4 KiB
Markdown
117 lines
1.4 KiB
Markdown
# 冒泡排序趟数期望
|
||
|
||
## 题目背景
|
||
|
||
Ran很喜欢【冒泡排序】，所以出了很多相关的题目，这又是其中一道。
|
||
|
||
对于一个排列 $a[1...n]$，进行一趟冒泡排序的代码为：
|
||
```cpp
|
||
for(int i=1;i<n;++i){
|
||
if(a[i]>a[i+1]) swap(a[i], a[i+1]);
|
||
}
|
||
```
|
||
若排列在 $k$ 趟冒泡排序之后变为有序，则最小的 $k$ 定义为 $res$。
|
||
|
||
## 题目描述
|
||
|
||
给一个长度为 $n$ 的随机排列（ $n!$ 种情况等概率出现），请你计算 $res$ 的期望值，对 `1e9+7` 取模。
|
||
|
||
例如 $n=3$:
|
||
- $a = [1,2,3], res = 0$
|
||
- $a = [1,3,2], res = 1$
|
||
- $a = [2,1,3], res = 1$
|
||
- $a = [2,3,1], res = 2$
|
||
- $a = [3,1,2], res = 1$
|
||
- $a = [3,2,1], res = 2$
|
||
|
||
期望为 $(0+1+1+2+1+2)/6 = 7/6$
|
||
|
||
## 输入格式
|
||
|
||
输入一行1个整数 $n$
|
||
|
||
## 输出格式
|
||
|
||
输出1个整数代表答案
|
||
|
||
## 样例 #1
|
||
|
||
### 样例输入 #1
|
||
|
||
```
|
||
3
|
||
```
|
||
|
||
### 样例输出 #1
|
||
|
||
```
|
||
166666669
|
||
```
|
||
|
||
## 样例 #2
|
||
|
||
### 样例输入 #2
|
||
|
||
```
|
||
10
|
||
```
|
||
|
||
### 样例输出 #2
|
||
|
||
```
|
||
801586487
|
||
```
|
||
|
||
## 样例 #3
|
||
|
||
### 样例输入 #3
|
||
|
||
```
|
||
50
|
||
```
|
||
|
||
### 样例输出 #3
|
||
|
||
```
|
||
123038582
|
||
```
|
||
|
||
## 样例 #4
|
||
|
||
### 样例输入 #4
|
||
|
||
```
|
||
12345
|
||
```
|
||
|
||
### 样例输出 #4
|
||
|
||
```
|
||
631836361
|
||
```
|
||
|
||
## 样例 #5
|
||
|
||
### 样例输入 #5
|
||
|
||
```
|
||
923456
|
||
```
|
||
|
||
### 样例输出 #5
|
||
|
||
```
|
||
276256848
|
||
```
|
||
|
||
## 提示
|
||
|
||
对于 20% 的数据，$n\le 8$
|
||
|
||
对于 40% 的数据，$n\le 16$
|
||
|
||
对于 60% 的数据，$n \le 3000$
|
||
|
||
对于 80% 的数据，$n \le 10^5$
|
||
|
||
对于 100% 的数据，$1\le n\le 10^6$ |