题目链接：点击打开链接
题意:
给定n ，k
下面n个数表示有一个n的排列，
每次操作等概率翻转一个区间，操作k次。
问：
k次操作后逆序数对个数的期望。
思路：
dp[i][j]表示 a[i] 在a[j] j前面的概率
初始就是 dp[i][j] = 1( i < j )
则对于翻转区间 [i, j], 出现的概率 P = 1 / ( n * (n+1) /2)
并且会导致 [i, j]内元素位置交换，枚举这次翻转的区间时所有的转移情况
#include <stdio.h> #include <string.h> #include <set>#include <map>#include <algorithm>#include <iostream>#include <vector>#include <string>#include <cmath>template <class T>inline bool rd(T &ret) {char c; int sgn;if (c = getchar(), c == EOF) return 0;while (c != '-' && (c<'0' || c>'9')) c = getchar();sgn = (c == '-') ? -1 : 1;ret = (c == '-') ? 0 : (c – '0');while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c – '0');ret *= sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if (x>9) pt(x / 10);putchar(x % 10 + '0');}using namespace std;typedef long long ll;const int N = 105;int n, m, a[N];double dp[N][N], tmp[N][N];int main(){while (cin >> n >> m){for (int i = 1; i <= n; i++)rd(a[i]);memset(dp, 0, sizeof dp);for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++)dp[i][j] = 1;double P = 1.0 / ( n * (n + 1) / 2.0 );while (m–){memcpy(tmp, dp, sizeof dp);memset(dp, 0, sizeof dp);for (int x = 1; x <= n; x++)for (int y = x; y <= n; y++){for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++){int a = i, b = j; //(i,j)在区间[x,y]对换后所对应的点为(a,b)if (x <= a && a <= y) a = x + y – a;if (x <= b && b <= y) b = x + y – b;//当且仅当区间[x, y]包含(i,j)时i>j变成j>i(而现在对应的位置是a,b)，否则是不变的if (a > b)swap(a, b);if (x <= i && j <= y)dp[a][b] += (1 – tmp[i][j])*P;elsedp[a][b] += tmp[i][j] * P;}}}double ans = 0;for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++){if (a[i] > a[j])ans += dp[i][j];elseans += 1 – dp[i][j];}printf("%.10f\n", ans);}return 0;}
，人生才会更有意义。如果没有梦想，那就托做庸人。
