「Codeforces 963E」Circles of Waiting 题解

题目

思路

设 \(f_{i,j}\) 为 \(\left(i,j\right)\) 移动到外面的期望步数

\(f_{i,j}=\begin{cases} 0 & ,i^2+j^2>R^2 \\ p_1f_{i-1,j}+p_2f_{i,j-1}+p_3f_{i+1,j}+p_4f_{i,j+1}+1 & ,i^2+j^2\le R^2 \end{cases}\)

直接消元是 \(\operatorname{O}(R^6)\) 的，不太行

考虑用每行第一个非零数这 \(2R+1\) 个数表达出所有数，从左到右从上到下枚举 \(f_{i+1,j}=\frac{f_{i,j}-p_1f_{i-1,j}-p_2f_{i,j-1}-p_4f_{i,j+1}-1}{p_3}\) 将每一个元的系数都按该式转移，对每行右侧第一个超出范围的有 \(f_{i+1,j}=0\)，于是可以得到 \(2R+1\) 个关于这 \(2R+1\) 个主元的方程，直接消元即可

时间复杂度 \(\operatorname{O}(R^3)\)

代码

const int N = 120;
const int M = 4005;
const int Mod = 1000000007;

int add(int a, int b) { a += b; if (a >= Mod) { a -= Mod; } return a; }
int sub(int a, int b) { a -= b; if (a < 0) { a += Mod; } return a; }
int pow(int a, int b, int m);
void work(int n);

int k[N][N][N];
int C[N][N];
int equ[N][N];
int lim[N];
int p1, p2, p3, p4;
int R, P;

int main () {
  read(R);
  P = R + 5;
  {
    read(p1), read(p2), read(p3), read(p4);
    int s = (p1 * 1ll + p2 + p3 + p4) % Mod;
    s = pow(s, Mod - 2, Mod);
    p1 = p1 * 1ll * s % Mod;
    p2 = p2 * 1ll * s % Mod;
    p3 = p3 * 1ll * s % Mod;
    p4 = p4 * 1ll * s % Mod;
  }
  for (int i = -R; i <= R; ++i) {
    lim[i + P] = int(sqrt(R * R - abs(i) * abs(i)) + 1);
    k[P - lim[i + P] + 1][i + P][i + R] = 1;
  }
  int ip3 = pow(p3, Mod - 2, Mod);
  for (int i = -R + 1; i <= R + 1; ++i) {
    for (int j = -R; j <= R; ++j) {
      if (i > -lim[j + P] + 1 && i <= lim[j + P]) {
        for (int l = 0; l <= 2 * R; ++l) {
          k[i + P][j + P][l] = sub(k[i - 1 + P][j + P][l], add(
            add(p1 * 1ll * k[i - 2 + P][j + P][l] % Mod, p2 * 1ll * k[i - 1 + P][j - 1 + P][l] % Mod),
            p4 * 1ll * k[i - 1 + P][j + 1 + P][l] % Mod
          )) * 1ll * ip3 % Mod;
        }
        C[i + P][j + P] = sub(C[i - 1 + P][j + P], add(
          add(p1 * 1ll * C[i - 2 + P][j + P] % Mod, p2 * 1ll * C[i - 1 + P][j - 1 + P] % Mod),
          add(p4 * 1ll * C[i - 1 + P][j + 1 + P] % Mod, 1)
        )) * 1ll * ip3 % Mod;
      }
    }
  }
  for (int i = -R; i <= R; ++i) {
    for (int l = 0; l <= 2 * R; ++l) {
      equ[i + R + 1][l + 1] = k[P + lim[i + P]][i + P][l];
    }
    equ[i + R + 1][2 * R + 2] = sub(0, C[P + lim[i + P]][i + P]);
  }
  work(2 * R + 1);
  int ans = 0;
  for (int l = 0; l <= 2 * R; ++l) {
    ans = add(ans, k[P][P][l] * 1ll * equ[l + 1][2 * R + 2] % Mod);
  }
  ans = add(ans, C[P][P]);
  write(ans), EL;
  return 0;
}

int pow(int a, int b, int m) {
  int ans = 1, now = a;
  while (b) {
    if (b & 1) {
      ans = ans * 1ll * now % m;
    }
    now = now * 1ll * now % m;
    b >>= 1;
  }
  return ans;
}
void work(int n) {
  for (int i = 1; i <= n; ++i) {
    int tmp = 0;
    for (int j = i; j <= n; ++j) {
      if (equ[j][i]) {
        tmp = j;
        break;
      }
    }
    if (tmp != i) {
      for (int j = i; j <= n + 1; ++j) {
        std::swap(equ[i][j], equ[tmp][j]);
      }
    }
    int iv = pow(equ[i][i], Mod - 2, Mod);
    for (int j = i; j <= n + 1; ++j) {
      equ[i][j] = equ[i][j] * 1ll * iv % Mod;
    }
    for (int j = i + 1; j <= n; ++j) {
      for (int k = n + 1; k >= i; --k) {
        equ[j][k] = sub(equ[j][k], equ[i][k] * 1ll * equ[j][i] % Mod);
      }
    }
  }
  for (int i = n - 1; i >= 1; --i) {
    for (int j = i + 1; j <= n; ++j) {
      equ[i][n + 1] = sub(equ[i][n + 1], equ[i][j] * 1ll * equ[j][n + 1] % Mod);
    }
  }
}