題意：

給出區間[1,n]的狀態，有0、1.現在每次可以選擇任意區間取翻轉，問全部翻轉成0的次數期望。總共有n(n+1)/2個區間。

題解：

這個CLJ鏈接將的很清楚了。

那么根據高斯消元列方程求解，因為有-2,+2，那么可以部除以2，這樣就變成-1,+1.

#include<iostream> #include<math.h> #include<stdio.h> #include<algorithm> #include<string.h> #include<string> #include<vector> #include<queue> #include<map> #include<set> #include<stack> #define B(x) (1<<(x)) using namespace std; typedef long long ll; typedef unsigned long long ull; const int oo = 0x3f3f3f3f; const ll OO = 0x3f3f3f3f3f3f3f3f; const double eps = 1e-9; #define lson rt<<1 #define rson rt<<1|1 void cmax(int& a, int b){ if (b > a)a = b; } void cmin(int& a, int b){ if (b < a)a = b; } void cmax(ll& a, ll b){ if (b > a)a = b; } void cmin(ll& a, ll b){ if (b < a)a = b; } void cmax(double& a, double b){ if (a - b < eps) a = b; } void cmin(double& a, double b){ if (b - a < eps) a = b; } void add(int& a, int b, int mod){ a = (a + b) % mod; } void add(ll& a, ll b, ll mod){ a = (a + b) % mod; } const ll MOD = 1000000007; const int maxn = 110000; double a[22][22]; int b[maxn];void Gauss(int n, int m){int r, c, k;for (r = c = 0; r < n && c < m; r++, c++){for (k = r; k < n; k++)if (fabs(a[k][c]) > eps)break;if (k == n) continue;if (k != r){for (int j = 0; j <= m; j++)swap(a[k][j], a[r][j]);}for (int j = c + 1; j <= m; j++)a[r][j] /= a[r][c];a[r][c] = 1.0;for (int i = 0; i < n; i++){if (i == r || fabs(a[i][c]) < eps) continue;for (int j = c + 1; j <= m; j++)a[i][j] -= a[i][c] * a[r][j];a[i][c] = 0.0;}} }void Init(int n){a[0][0] = 1.0;for (int i = 2; i <= n + 1; i += 2){a[i / 2][i / 2] = 1 - 2.0 * i * (n + 1 - i) / n / (n + 1);a[i / 2][i / 2 - 1] -= 1.0 * i * (i - 1) / n / (n + 1);a[i / 2][i / 2 + 1] -= 1.0 * (n + 1 - i) * (n - i) / n / (n + 1);a[i / 2][(n + 1) / 2 + 1] = 1.0;} }int main(){//freopen("E:\\read.txt", "r", stdin);int n, c;while (scanf("%d", &n) != EOF){c = 0;b[0] = b[n + 1] = 0;for (int i = 1; i <= n; i++){scanf("%d", &b[i]);c += (b[i] ^ b[i - 1]);}c += b[n + 1] ^ b[n];Init(n);n = (n + 1) / 2 + 1;Gauss(n, n);printf("%.6lf\n", a[c / 2][n] / a[c / 2][c / 2]);}return 0; }

總結

以上是生活随笔為你收集整理的hihoCoder 1166 交换代数 (高斯消元，概率)的全部內容，希望文章能夠幫你解決所遇到的問題。

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