danihao123's Blog

逆矩阵文明，，，

很显然我们可以定义一个状态\(f[i][j]\)表示当前血量为\(i\)走到\(j\)的概率，然后肥肠爆歉这个东西没法DP（可能会有的点的伤害为0，这样可以凿出来环）。考虑高消，这个东西有个好处是不可能从血量低的到血量高的状态，所以可以从大到小枚举血量，这样各层事独立的，复杂度比直接高消降低了很少。可惜复杂度为\(O(sn^3)\)（设血量为\(s\)），会T掉。

考虑转移的过程，转移时等价于解这样一个方程：

\[
\begin{aligned}
a_{11}x_{1} + a_{12}x_{2} + \ldots + a_{1n}x_{n} &= c_1\\
a_{21}x_{1} + a_{22}x_{2} + \ldots + a_{2n}x_{n} &= c_2\\
&\ldots\\
a_{n1}x_{1} + a_{n2}x_{2} + \ldots + a_{nn}x_{n} &= c_n
\end{aligned}
\]

其中的未知数\(x\)事我们要求的东西，\(c\)表示从高血量状态转移过来的概率（这个可以视作常数）。根据友矩阵那一套理论，这一系列方程等价于以下等式：

\[
\begin{bmatrix}
a_{11} & a_{12} & \ldots & a_{1n}\\
a_{21} & a_{22} & \ldots & a_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & \ldots & a_{nn}
\end{bmatrix}
\begin{bmatrix}
x_{1}\\ x_{2} \\ \vdots \\ x_{n}
\end{bmatrix}
=
\begin{bmatrix}
c_1\\ c_2\\ \vdots\\ c_n
\end{bmatrix}
\]

不妨将之简记为\(AB = C\)，其中我们只有\(B\)不知道，要求的也是\(B\)。我们除一下就可以得到\(B = A^{-1}C\)，然后我们还发现每一层的\(A\)都是一样的，所以每一层的\(A^{-1}\)也都是一样的，预处理即可。这样转移部分的复杂度就变成了\(O(sn^2)\)（矩阵乘法在这里事方阵乘列向量）。

至于逆矩阵的求法，我们知道对矩阵做初等变化也就等价于乘上另一个矩阵。因此，我们将一个矩阵\(A\)用类似于高消的手段消为单位阵\(I\)，所做的初等变换也就等价于乘上\(A^{-1}\)。我们对一个单位阵\(I\)作用上一样的操作，也就等于给这个单位阵乘上了\(A^{-1}\)，这样我们就得到了\(A^{-1}\)。

代码：

/**************************************************************
    Problem: 3640
    User: danihao123
    Language: C++
    Result: Accepted
    Time:8708 ms
    Memory:13416 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
#include <set>
#include <map>
int n, m, hp;
const int maxn = 151, maxm = 5005;
const int maxh = 10005;
typedef double R;
typedef R Mat[maxn][maxn];
Mat D, F;
void calc_inv() {
  for(int i = 1; i <= n; i ++) {
    F[i][i] = 1;
  }
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    // assert(r > -1);
    if(r != i) {
      for(int j = 1; j <= n; j ++) {
        std::swap(D[r][j], D[i][j]);
        std::swap(F[r][j], F[i][j]);
      }
    }
    R bs = D[i][i];
    for(int j = 1; j <= n; j ++) {
      D[i][j] /= bs; F[i][j] /= bs;
    }
    for(int k = 1; k <= n; k ++) {
      if(k != i) {
        R rate = D[k][i];
        for(int j = 1; j <= n; j ++) {
          D[k][j] -= rate * D[i][j];
          F[k][j] -= rate * F[i][j];
        }
      }
    }
  }
}
void matrix_mul(const Mat &A, const Mat &B, int a, int b, int c, Mat &res) {
  static Mat C;
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      C[i][j] = 0;
    }
  }
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      for(int k = 1; k <= b; k ++) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  for(int i = 1; i <= a; i ++) {
    for(int j = 1; j <= c; j ++) {
      res[i][j] = C[i][j];
    }
  }
}
 
int first[maxn], deg[maxn];
int next[maxm << 1], to[maxm << 1];
int gcnt = 0;
void add_edge(int u, int v) {
  gcnt ++;
  next[gcnt] = first[u]; first[u] = gcnt;
  to[gcnt] = v;
}
void ins_edge(int u, int v) {
  deg[u] ++;
  add_edge(u, v);
  if(u != v) {
    deg[v] ++;
    add_edge(v, u);
  }
}
 
int atk[maxn];
R f[maxh][maxn];
R solve() {
  for(int i = 1; i <= n; i ++) {
    D[i][i] = 1.00;
  }
  for(int i = 1; i < n; i ++) {
    for(int j = first[i]; j; j = next[j]) {
      int v = to[j];
      if(!atk[v]) {
        D[v][i] -= 1.00 / (R(deg[i]));
      }
    }
  }
  calc_inv();
  R ans = 0; static Mat C;
  f[hp][1] = 1.00;
  for(int i = hp; i >= 1; i --) {
    for(int j = 1; j <= n; j ++) {
      C[j][1] = f[i][j];
    }
    matrix_mul(F, C, n, n, 1, C);
    for(int j = 1; j < n; j ++) {
      for(int e = first[j]; e; e = next[e]) {
        int v = to[e];
        if(atk[v] > 0 && i - atk[v] > 0) {
          f[i - atk[v]][v] += C[j][1] / (R(deg[j]));
        }
      }
    }
    ans += C[n][1];
  }
  return ans;
}
 
int main() {
  scanf("%d%d%d", &n, &m, &hp);
  for(int i = 1; i <= n; i ++) {
    scanf("%d", &atk[i]);
  }
  for(int i = 1; i <= m; i ++) {
    int u, v; scanf("%d%d", &u, &v);
    ins_edge(u, v);
  }
  printf("%.8lf\n", solve());
  return 0;
}

本野蛮人竟然没做过高消期望DP，，，泪，流了下来，，，

根据期望线性性，答案就是所有边的期望被走的次数乘上边的编号的和。一条边期望经过的次数可以根据他两个端点期望经过的次数来算（但是\(n\)要特判一下），要求所有点期望走过的次数当然就可以列\(n\)个方程然后高消力。然后期望走的次数多的边编号应该小，反之亦然，所以求完每条边走的次数的期望之后就贪心一下就好力。

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <utility>
#include <cmath>
const int maxn = 505;
const int maxm = maxn * maxn;
using R = double;
const R eps = 1e-9;
int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    return ((x < 0.00) ? -1 : 1);
  }
}
R D[maxn][maxn];
int n;
void gauss() {
#ifdef LOCAL
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n + 1; j ++) {
      printf("%.3lf ", D[i][j]);
    }
    puts("");
  }
#endif
  for(int i = 1; i <= n; i ++) {
    int r = i;
    for(int j = i + 1; j <= n; j ++) {
      if(fabs(D[j][i]) > fabs(D[r][i])) {
        r = j;
      }
    }
    assert(sign(D[r][i]) != 0);
    if(r != i) {
      for(int j = 1; j <= n + 1; j ++) {
        std::swap(D[i][j], D[r][j]);
      }
    }
    for(int k = i + 1; k <= n; k ++) {
      R rate = D[k][i] / D[i][i];
      for(int j = i; j <= n + 1; j ++) {
        D[k][j] -= D[i][j] * rate;
      }
    }
  }
  for(int i = n; i >= 1; i --) {
    for(int j = i + 1; j <= n; j ++) {
      D[i][n + 1] -= D[j][n + 1] * D[i][j];
      D[i][j] = 0;
    }
    D[i][n + 1] /= D[i][i]; D[i][i] = 1;
#ifdef LOCAL
    printf("E[%d] : %.3lf\n", i, D[i][n + 1]);
#endif
  }
}

int E[maxm][2], deg[maxn];
R tms[maxm];
void add_edge(int u, int v) {
  if(u != n) D[v][u] += 1.00 / (R(deg[u]));
}

int main() {
  int m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    D[i][i] = -1;
  }
  D[1][n + 1] = -1;
  for(int i = 1; i <= m; i ++) {
    scanf("%d%d", &E[i][0], &E[i][1]);
    deg[E[i][0]] ++; deg[E[i][1]] ++;
  }
  for(int i = 1; i <= m; i ++) {
    int u = E[i][0], v = E[i][1];
    add_edge(u, v); add_edge(v, u);
  }
  gauss();
  for(int i = 1; i <= m; i ++) {
    tms[i] = 0;
    int u = E[i][0], v = E[i][1];
    if(u != n) tms[i] += D[u][n + 1] / (R(deg[u]));
    if(v != n) tms[i] += D[v][n + 1] / (R(deg[v]));
  }
  std::sort(tms + 1, tms + 1 + m, [&](const R &i, const R &j) { return i > j; });
  R ans = 0;
  for(int i = 1; i <= m; i ++) {
    ans += tms[i] * (R(i));
  }
  printf("%.3lf\n", ans);
  return 0;
}

ao劲啊这题，，，

看到那个逆序对奇偶性就想到了行列式（考虑行列式的定义）……其实最后要判定的就是该矩阵行列式的正负性（或者是0）。

这个东西肯定可以高消搞成上三角，然后行列式就很好求了。但高消事\(O(n^3)\)的，会T掉。

考虑怎么去优化这个高消。首先在消元顺序合理的情况下，一定可以让矩阵在整个过程中一直是01矩阵。具体的实现方式，就是考虑从小到大对每个变量进行消元的时候，包含该变量的方程很多，并且他们两两之间一定是满足一个的全1段事另一个的前缀。那么用最短的那一段进行消元即可。

考虑到其他方程被消之后最靠左的1的位置会全部变成另一个位置，所以可以考虑使用可并堆维护各个方程。同时，为了求每个方程当前最靠左的1的位置，我搞了个并查集（逃

代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
#include <ext/pb_ds/priority_queue.hpp>
using R = double;
// using GG = __gnu_pbds::priority_queue<int>;
const int maxn = 100005;
const R eps = 1e-8;
inline int sign(R x) {
  if(fabs(x) < eps) {
    return 0;
  } else {
    if(x < 0.00) {
      return -1;
    } else {
      return 1;
    }
  }
}
 
int seg[maxn][2];
namespace BF {
  R A[105][105];
  inline int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      int r = i;
      for(int j = i + 1; j <= n; j ++) {
        if(fabs(A[j][i]) > fabs(A[i][i])) {
          r = j;
        }
      }
      if(r != i) {
        flag *= -1;
        for(int j = i; j <= n; j ++) {
          std::swap(A[i][j], A[r][j]);
        }
      } else {
        if(sign(A[i][i]) == 0) {
          return 0;
        }
      }
      for(int j = i + 1; j <= n; j ++) {
        if(sign(A[j][i]) == 0) continue;
        double f = A[j][i] / A[i][i];
        for(int k = i; k <= n; k ++) {
          A[j][k] -= A[i][k] * f;
        }
      }
    }
    int ret = flag;
    for(int i = 1; i <= n; i ++) {
      ret *= sign(A[i][i]);
    }
    return ret;
  }
  inline void solve(int n) {
    for(int i = 1; i <= n; i ++) {
      int L = seg[i][0], R = seg[i][1];
      for(int j = 1; j <= n; j ++) {
        if(L <= j && j <= R) {
          A[i][j] = 1;
        } else {
          A[i][j] = 0;
        }
      }
    }
    int v = (det(n));
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
namespace CT {
  /*
  struct Node {
    int l, r, id;
    bool operator <(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id < res.id;
        } else {
          return r < res.r;
        }
      } else {
        return l < res.l;
      }
    }
    bool operator >(const Node &res) const {
      if(l == res.l) {
        if(r == res.r) {
          return id > res.id;
        } else {
          return r > res.r;
        }
      } else {
        return l > res.l;
      }
    }
    bool operator ==(const Node &res) const {
      return (l == res.l) && (r == res.r) && (id == res.id);
    }
  };
  */
  struct N2 {
    int r, id;
    N2() {
      r = 0; id = 0;
    }
    N2(int x, int y) {
      r = x; id = y;
    }
    bool operator <(const N2 &res) const {
      if(r == res.r) {
        return id < res.id;
      } else {
        return r < res.r;
      }
    }
    bool operator >(const N2 &res) const {
      if(r == res.r) {
        return id > res.id;
      } else {
        return r > res.r;
      }
    }
    bool operator ==(const N2 &res) const {
      return (r == res.r) && (id == res.id);
    }
  };
  
  /* struct Node {
    Node *fa, *ch[2];
    N2 v; int l;
    int setv;
    int d() {
      return ((this == fa -> ch[1]) ? 1 : 0);
    }
    void sc(Node *c, int dir) {
      ch[dir] = c;
      c -> fa = this;
    }
    int cmp(const N2 &v2) const {
      if(v == v2) {
        return -1;
      } else {
        if(v2 < v) {
          return 0;
        } else {
          return 1;
        }
      }
    }
    void paint(int x) {
      if(l == -1) return;
      l = x; setv = x;
    }
    void pushdown(int x) {
      if(setv != -1) {
        ch[0] -> paint(setv);
        ch[1] -> paint(setv);
        setv = -1;
      }
    }
  };
  Node pool[maxn]; std::queue<int> FQ;
  Node *nil, *cur;
  void init_pool() {
    nil = cur = pool;
    nil -> l = nil -> setv = -1;
    nil -> fa = nil -> ch[0] = nil -> ch[1] = nil;
  }
  Node *alloc_node(N2 x, int L) {
    Node *ret;
    if(FQ.empty()) {
      ret = ++ cur;
    } else {
      ret = FQ.front(); FQ.pop();
    }
    ret -> v = x;
    ret -> l = L; ret -> setv = -1;
    ret -> fa = ret -> ch[0] = ret -> ch[1] = nil;
    return ret;
  }
  
  inline bool is_root(Node *o) {
    return (o -> fa == nil)
  }
  inline void zig(Node *x) {
    int d = x -> d(); Node *y = x -> fa;
    if(is_root(y)) {
      x -> fa = y -> fa;
    } else {
      y -> fa -> sc(x, y -> d());
    }
    y -> sc(x -> ch[d ^ 1], d);
    x -> sc(y, d ^ 1);
  }
  void pdw_path(Node *x) {
    if(!is_root(x)) pdw_path(x -> fa);
    x -> pushdown();
  }
  inline void splay(Node *x) {
    pdw_path(x);
    while(!is_root(x)) {
      Node *y = x -> fa;
      if(!is_root(y)) {
        if((x -> d()) ^ (y -> d())) {
          zig(x);
        } else {
          zig(y);
        }
      }
      zig(x);
    }
  }
  Node *insert(Node *o, Node *x) {
    if(o == nil) return x;
    Node *last = o;
    int d;
    while(o != nil) {
      o -> pushdown(); last = o;
      d = o -> cmp(x -> v);
      o = o -> ch[d];
    }
    x -> ch[0] = x -> ch[1] = nil;
    last -> sc(x, d);
    splay(x); return x;
  }
  Node *top(Node *x) {
    Node *ret = x;
    while(x -> ch[0] == 0) {
      x -> paint
    }
  } */
  
  int par[maxn * 2];
  int get_fa(int x) {
    if(par[x] == x) return x;
    else return (par[x] = get_fa(par[x]));
  }
  void merge(int dir, int src) {
    dir = get_fa(dir); src = get_fa(src);
    if(dir == src) return;
    par[src] = dir;
  }
  bool is_same(int x, int y) {
    return (get_fa(x) == get_fa(y));
  }
  
  using heap = __gnu_pbds::priority_queue<N2, std::greater<N2> >;
  heap Q[maxn];
  int id[maxn], mp[maxn];
  int det(int n) {
    int flag = 1;
    for(int i = 1; i <= n; i ++) {
      Q[i].clear();
    }
    for(int i = 1; i <= 2 * n; i ++) {
      par[i] = i;
    }
    for(int i = 1; i <= n; i ++) {
      id[i] = mp[i] = i;
      int L = seg[i][0], R = seg[i][1];
      Q[L].push(N2(R, i));
      merge(L, n + i);
    }
    for(int i = 1; i <= n; i ++) {
      if(Q[i].empty()) {
        return 0;
      }
      int p = id[i];
      if(!(get_fa(p + n) <= i && seg[p][1] == (Q[i].top()).r)) {
        flag *= -1;
        int np = (Q[i].top()).id;
#ifdef LOCAL
        printf("Swaping %d and %d.\n", p, np);
#endif
        int nv = mp[np];
        std::swap(id[i], id[nv]);
        std::swap(mp[np], mp[p]);
      }
      p = id[i];
      Q[i].pop();
      int r = seg[p][1];
      if(Q[i].size() > 0 && (Q[i].top()).r == r) {
        return 0;
      }
      if(r < n) {
        Q[r + 1].join(Q[i]);
        merge(r + 1, i);
      }
    }
    return flag;
  }
  void solve(int n) {
    int v = det(n);
    if(v == -1) {
      puts("Fedor");
    } else if(v == 0) {
      puts("Draw");
    } else {
      puts("Alex");
    }
  }
};
 
int main() {
  int T; scanf("%d", &T);
  while(T --) {
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; i ++) {
      scanf("%d%d", &seg[i][0], &seg[i][1]);
    }
    if(n <= 100) {
      BF::solve(n);
    } else {
      CT::solve(n);
    }
  }
  return 0;
}

不行不能颓了……线代其实刚起步……

注意每个点到球心的距离相同，距离之平方亦相同。然后假设所有半径平方为[tex]d[/tex]，那么我们先可以列出两个方程（假设[tex]n=2[/tex]，不过此时事实上可以列三个，但出于方便讨论的目的便只列两个）：

[tex](x_1-a_1)^2+(x_2-a_2)^2=d[/tex]

[tex](x_1-b_1)^2+(x_2-b_2)^2=d[/tex]

两方程作差，得：

[tex](x_1-a_1)^2+(x_2-a_2)^2-(x_1-b_1)^2-(x_2-b_2)^2=0[/tex]

整理，得：

[tex]2(b_1-a_1)x_1+2(b_2-a_2)x_2=(b_1+a_1)(b_1-a_1)+(b_2+a_2)(b_2-a_2)[/tex]

对这种方法加以推广，便可列出[tex]n[/tex]个[tex]n[/tex]元一次方程。高斯消元求解即可。

代码：

/**************************************************************
    Problem: 1013
    User: danihao123
    Language: C++
    Result: Accepted
    Time:4 ms
    Memory:1296 kb
****************************************************************/
 
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
double M[maxn][maxn];
double A[maxn][maxn];
inline void Gause(){
    register int i,j,k,r;
    register double f;
    for(i=1;i<=n;i++){
        r=i;
        for(j=i+1;j<=n;j++)
            if(fabs(A[j][i])>fabs(A[r][i]))
                r=j;
        if(r!=i)
            for(j=1;j<=(n+1);j++)
                swap(A[r][j],A[i][j]);
        for(k=i+1;k<=n;k++){
            f=A[k][i]/A[i][i];
            for(j=i;j<=n+1;j++)
                A[k][j]-=f*A[i][j];
        }
    }
    for(i=n;i>=1;i--){
        for(j=i+1;j<=n;j++)
            A[i][n+1]-=A[j][n+1]*A[i][j];
        A[i][n+1]/=A[i][i];
    }
}
int main(){
    register int i,j;
    bool flag=false;
    cin>>n;
    for(i=1;i<=(n+1);i++)
        for(j=1;j<=n;j++)
            cin>>M[i][j];
    for(i=1;i<=n;i++)
        for(j=1;j<=(n+1);j++)
            A[i][j]=0;
    for(i=1;i<=n;i++){
        for(j=1;j<=n;j++){
            A[i][j]=2*(M[i+1][j]-M[i][j]);
            A[i][n+1]+=(M[i+1][j]-M[i][j])*(M[i+1][j]+M[i][j]);
        }
    }
    Gause();
    for(i=1;i<=n;i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%.3f",A[i][n+1]);
    }
    putchar('\n');
    return 0;
}