CF1286D LCC

题意：一条无限长的管道中有 个粒子，第 个粒子的位置为 。

一次实验开始时，第 个粒子会获得 的初速度并匀速运动，有 的概率向右移动， 的概率向左移动。

当任意两个粒子移动到相同位置的时候会发生碰撞。

设该实验所消耗的时间为第一次发生碰撞的时间。若不会发生碰撞，则认为这次实验耗费的时间为 。

求一次实验期望耗费的时间，对 取模。

，时限 。

---

不难发现，第一次发生碰撞的两个点一定是初始时相邻的两个点。

若有多个碰撞同时发生，则按球的编号为序。

于是，可以枚举发生碰撞的两个点，以及这两个点的方向，并计算这样的概率。（若不可能碰撞则不忽略）

我们钦定的碰撞发生时间为 ，则前面的相邻点对碰撞时间 ，后面的相邻点对碰撞时间 。

考虑利用 来判定，设 表示考虑了前 个粒子，最后一个粒子的方向为 时满足限制的概率。

（需要对一个前缀和一个后缀分别计算，也可以大力修改转移）

考虑将转移写成矩阵，将询问的时间 从小到大排序后，共会导致 次矩阵的修改。用线段树维护即可。

复杂度 。