「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);
}

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2020/CF-1286D/