锐客网

  1. 首页 > it技术 > >

数学|【Topcoder SRM 641】BitToggler 期望 高斯消元

数学Topcoder

有一个长度为n的01数列a和一个指针，每次随机将指针移至j，并将aj取反，花费为|i - j|，当数列全0或全1停止，求期望花费。n <= 20
使用期望的线性性，每次只统计i到j的贡献，这样其他位置就没有区分了，压个状态就可以消元了。


【数学|【Topcoder SRM 641】BitToggler 期望 高斯消元】

#include #include #include #include #include #include #define Rep(i, x, y) for (int i = x; i <= y; i ++) #define Dwn(i, x, y) for (int i = x; i >= y; i --) #define RepE(i, x) for(int i = pos[x]; i; i = g[i].nex) #define eps 0.000000001 using namespace std; typedef long long LL; typedef double DB; const int M = 330; int n, m, Q; DB a[M][M], sum; vector ans; void PreWork() { m = (n - 1) * 16; DB p1 = 1.0 / n; Rep(i, 0, 1) { Rep(j, 0, 1) { Rep(k, 0, n - 2) { int s = (k * 4 + i * 2 + j) * 4; if (!s || s == (n - 2) * 16 + 12) { Rep(t, 0, 3) a[s + t][s + t] = 1; continue ; } Rep(t, 0, 3) { a[s + t][s + t] = 1; a[s + t][s ^ 8] = -p1; a[s + t][(s ^ 4) + 1] = -p1; if (k) a[s + t][s - 14] = -p1 * k; if (k < n - 2) a[s + t][s + 19] = -p1 * (n - 2 - k); } a[s][m] = p1; } } } Rep(i, 1, m - 1) { int k = i; while (k < m && fabs(a[k][i]) < eps) k ++; if (k >= m) { continue ; } Rep(j, 1, m) swap(a[i][j], a[k][j]); Rep(j, 1, m - 1) if (i != j && a[j][i]) { DB z = a[j][i] / a[i][i]; Rep(x, 1, m) a[j][x] -= z * a[i][x]; } } } class BitToggler { public: vector expectation(int n0, vectorbits, vector pos) { Q = bits.size(), n = n0; PreWork(); Rep(T0, 0, Q - 1) { sum = 0; int num = 0, k, s; Rep(i, 0, n - 1) num += (bits[T0][i] == '1'); Rep(i, 0, n - 1) { Rep(j, 0, n - 1) if (i != j) { if (i == pos[T0]) k = 0; else if (j == pos[T0]) k = 1; else if (bits[T0][ pos[T0] ] == '0') k = 2; else k = 3; bool x1 = (bits[T0][i] == '1'), x2 = (bits[T0][j] == '1'); s = ((num - x1 - x2) * 4 + x1 * 2 + x2) * 4 + k; sum += a[s][m] / a[s][s] * abs(i - j); } } ans.push_back(sum); } return ans; } };




    推荐阅读


    上一篇：字符串|【VOJ1895】 ニニスの守護 后缀数组 DP

    下一篇：hdu|【hdu 5354】Bipartite Graph【分治 并查集】