标签：概率 粒子 碰撞 solution times bmatrix cf1286d dp

CF1286D Solution

link

题面：有 \(n\) 个粒子，第 \(i\) 个粒子在位置 \(x_i\) 并有 \(v_i\) 的初速度。

实验开始后，第 \(i\) 个粒子有 \(p_i\) 的概率向右移动，有 \(1-p_i\) 的概率向左移动。

求第一次发生粒子碰撞的期望时间，对 \(998244353\) 取模。

\(n\le10^5,|x_i|\le10^9\)。

---

显然，首先第一次发生碰撞的粒子必定一开始是相邻的。

那么现在我们只需要考虑 \(n-1\) 对相邻粒子之间的碰撞情况。

由于每种粒子只有可能向左或向右，那么情况数是 \(\mathcal O(n)\) 的。

考虑把所有情况找出来，钦定它是第一次发生的碰撞并计算概率。

这个概率就是所有比它碰撞时间早的碰撞事件都不发生的概率，乘上这一次碰撞发生的概率。

先考虑对于每个碰撞做一次 dp 求出前者。假设此次碰撞为 \(C\)。

设 \(dp_{i,0/1}\) 表示前 \(i\) 个粒子不在 \(C\) 之前发生碰撞，第 \(i\) 个粒子的方向为 \(0/1\) 的概率。

\(f(i,0/1,0/1)\) 表示 \(i\) 方向为 \(0/1\)，\(i+1\) 方向为 \(0/1\) 导致的 \(i\) 和 \(i+1\) 的碰撞是否在 \(C\) 后发生。（不发生为 \(1\)）

转移：

\[dp_{i,0}\gets (1-p_{i})(dp_{i-1,0}\times f(i-1,0,0)+dp_{i-1,1}\times f(i-1,1,0)) \]

\[dp_{i,1}\gets p_{i}(dp_{i-1,0}\times f(i-1,0,1)+dp_{i-1,1}\times f(i-1,1,1)) \]

这个可以写成矩阵转移，如下：

\(\begin{bmatrix} dp_{i-1,0}&dp_{i-1,1} \end{bmatrix} \times \begin{bmatrix} (1-p_{i})f(i-1,0,0)&p_{i}f(i-1,0,1)\\ (1-p_{i})f(i-1,1,0)&p_{i}f(i-1,1,1) \end{bmatrix} =\begin{bmatrix} dp_{i,0}&dp_{i,1} \end{bmatrix}\)

现在的复杂度是 \(\mathcal O(n^2)\) 的，因为每次的转移矩阵都不同。

考虑不同的 \(C\) 的转移矩阵的变化。我们把所有 \(C\) 按照发生的时间排序，然后你发现对于相邻的 \(C\)，仅有一个 \(f\) 会发生变化，也就是这次碰撞对应的 \(f\)。

那么就好办了，由于只有一个 \(f\) 发生变化，我们只需要修改它所在的转移矩阵，用线段树维护矩阵乘积即可。

查询时可以直接用前 \(i-1\) 个碰撞事件不发生的概率减去前 \(i\) 个碰撞事件不发生的概率。

复杂度线性对数。

标签：概率,粒子,碰撞,solution,times,bmatrix,cf1286d,dp
From： https://www.cnblogs.com/iorit/p/18040095