「Codeforces 1286D」LCC 题解

题目

思路

容易证明，第一次碰撞的粒子初始位置是相邻的，考虑钦定一对粒子的运动方向，计算在它们相撞前，其他粒子都不相撞的概率

设 \(f_{i,j,0/1,0/1}\) 为第 \(i\) 到 \(j\) 个粒子，第 \(i-1\) 个向左/右，第 \(j\) 个向左/右，满足在钦定粒子相撞前不相撞的概率（可以人为添加一个速度无穷大，向左运动的粒子 \(0\)），于是答案为 \(f_{1,n,0,0}+f_{1,n,0,1}\)

发现转移是这样的：\(f_{i,j,s_1,s_2}=\sum_{s_3}f_{i,k,s_1,s_3}f_{k,j,s_3,s_2}\)，其中 \(k\) 可以任取，显然是个矩阵乘法的形式

设第 \(i\) 个粒子的矩阵为 \(M_i\)，若 \(i-1\) 向左，\(i\) 向左会在钦定前相撞，则 \(M_{i,0,0}=0\)，否则 \(M_{i,0,0}=1-p_i\)，其他情况类似

考虑将所有可能相撞的情形按相撞时间升序排序，处理时将 \(M_i\) 只保留钦定的一种情况，其他的置为 \(0\)，将所有矩阵相乘统计答案，再还原 \(M_i\) 并将钦定的情况置为 \(0\)（之后的情形中这种运动方向会先碰撞是不满足条件的）

单点修改，全局查询矩阵乘法用线段树维护即可

时间复杂度 \(\operatorname{O}(n\log n)\)

代码

const int N = 100005;
const int Mod = 998244353;

class Matrix {
public:
  int a[2][2];
  Matrix() {
    a[0][0] = a[0][1] = a[1][0] = a[1][1] = 0;
  }
  Matrix & operator =(Matrix i) {
    a[0][0] = i.a[0][0];
    a[0][1] = i.a[0][1];
    a[1][0] = i.a[1][0];
    a[1][1] = i.a[1][1];
    return *this;
  }
  Matrix operator *(Matrix i) {
    Matrix ans;
    ans.a[0][0] = (a[0][0] * 1ll * i.a[0][0] + a[0][1] * 1ll * i.a[1][0]) % Mod;
    ans.a[0][1] = (a[0][0] * 1ll * i.a[0][1] + a[0][1] * 1ll * i.a[1][1]) % Mod;
    ans.a[1][0] = (a[1][0] * 1ll * i.a[0][0] + a[1][1] * 1ll * i.a[1][0]) % Mod;
    ans.a[1][1] = (a[1][0] * 1ll * i.a[0][1] + a[1][1] * 1ll * i.a[1][1]) % Mod;
    return ans;
  }
};
class Query {
public:
  int s, v, x, a, b;
  Query(int s = 0, int v = 0, int x = 0, int a = 0, int b = 0) : s(s), v(v), x(x), a(a), b(b) {}
  bool operator<(Query i) {
    return s * 1ll * i.v < i.s * 1ll * v;
  }
};

int pow(int a, int b, int m);
void build(int x, int xl, int xr);
void update(int x, int xl, int xr, int ux);

Matrix sum[N << 2];
Matrix m[N];
int x[N], v[N], p[N];
Query q[N << 1];
int cnt;
int n;

int main () {
  read(n);
  int iv = pow(100, Mod - 2, Mod);
  for (int i = 1; i <= n; ++i) {
    read(x[i]), read(v[i]), read(p[i]);
    p[i] = p[i] * 1ll * iv % Mod;
  }
  for (int i = 1; i <= n; ++i) {
    m[i].a[0][0] = m[i].a[1][0] = (Mod + 1 - p[i]) % Mod;
    m[i].a[0][1] = m[i].a[1][1] = p[i];
  }
  build(1, 1, n);
  for (int i = 2; i <= n; ++i) {
    q[++cnt] = Query(x[i] - x[i - 1], v[i] + v[i - 1], i, 1, 0);
    if (v[i] > v[i - 1]) {
      q[++cnt] = Query(x[i] - x[i - 1], v[i] - v[i - 1], i, 0, 0);
    }
    if (v[i] < v[i - 1]) {
      q[++cnt] = Query(x[i] - x[i - 1], v[i - 1] - v[i], i, 1, 1);
    }
  }
  std::sort(q + 1, q + cnt + 1);
  int res = 0;
  for (int i = 1; i <= cnt; ++i) {
    Matrix m1, m2;
    m1 = m[q[i].x];
    m2.a[q[i].a][q[i].b] = m1.a[q[i].a][q[i].b];
    m[q[i].x] = m2;
    update(1, 1, n, q[i].x);
    int tim = q[i].s * 1ll * pow(q[i].v, Mod - 2, Mod) % Mod;
    res = (res + (sum[1].a[0][0] + sum[1].a[0][1]) * 1ll * tim % Mod) % Mod;
    m1.a[q[i].a][q[i].b] = 0;
    m[q[i].x] = m1;
    update(1, 1, n, q[i].x);
  }
  write(res), 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 pushup(int x) {
  sum[x] = sum[x << 1] * sum[x << 1 | 1];
}
void build(int x, int xl, int xr) {
  if (xl == xr) {
    sum[x] = m[xl];
    return;
  }
  int xm = (xl + xr) >> 1;
  build(x << 1, xl, xm);
  build(x << 1 | 1, xm + 1, xr);
  pushup(x);
}
void update(int x, int xl, int xr, int ux) {
  if (xl == xr) {
    sum[x] = m[xl];
    return;
  }
  int xm = (xl + xr) >> 1;
  if (ux <= xm) {
    update(x << 1, xl, xm, ux);
  } else {
    update(x << 1 | 1, xm + 1, xr, ux);
  }
  pushup(x);
}