提交记录：https://qoj.ac/submission/3345845

AI Disclosure：全是 Argon 干的。人类修复了 typo。

官方做法只能做到 $O(nm^2)$？玩的太差了。可以进一步优化。通过阿贝尔变换（尾概率积分公式）消去退背包操作，再结合分治 NTT（Divide & Conquer NTT），可以将时间复杂度从 $O(nm^2)$ 降至 $O(nm \log(\min(n, m)) + nm \log^3 m)$，摆脱对 $m^2$ 的依赖。

1. 期望公式转化：从“逐次退背包”到“全局线性组合”

设将所有 $nm$ 个到达时间从小到大排序后为 $u_1 \le u_2 \le \dots \le u_{nm}$。 对于非负随机变量 $T$（中位数到达原点的时间），利用尾概率期望公式：

$$\mathbb{E}[T] = \int_0^\infty \mathbb{P}(T > t)\,dt = u_1 + \sum_{r=1}^{nm-1} (u_{r+1} - u_r) \cdot \mathbb{P}(T > u_r)$$

（注：当 $t < u_1$ 时 $\mathbb{P}(T > t) = 1$；当 $t \ge u_{nm}$ 时所有弹珠均已到达原点，$\mathbb{P}(T > t) = 0$；若 $u_{r+1} = u_r$，对应项系数为 $0$，天然兼容重根。）

在扫描完第 $r$ 个事件后，设第 $i$ 个弹珠已有 $c_i^{(r)}$ 个起点的到达时间 $\le u_r$，对应的状态多项式为：

$$F_r(z) = \prod_{i=1}^m L_{c_i^{(r)}}(z), \quad \text{其中 } L_c(z) = (n - c) + c z$$

此时 $T > u_r$ 等价于到达原点的弹珠数严格小于 $k = \frac{m+1}{2}$，即：

$$\mathbb{P}(T > u_r) = \frac{1}{n^m} \sum_{d=0}^{k-1} [z^d] F_r(z)$$

利用线性性质交换求和号，我们不再需要在每一步做退背包求单个系数，而是只需要求出所有 $F_r(z)$ 的线性组合多项式：

$$\Phi(z) = \sum_{r=1}^{nm-1} w_r F_r(z), \quad \text{其中常数 } w_r = (u_{r+1} - u_r) \bmod P$$

最后仅需在结尾做一次前 $k-1$ 项系数求和：

$$\mathbb{E}[T] = \left(u_1 + \frac{1}{n^m} \sum_{d=0}^{k-1} [z^d] \Phi(z)\right) \bmod P$$

2. 分治 NTT：提取区间不变量

直接求 $\sum_{r=1}^{nm-1} w_r F_r(z)$ 的瓶颈在于每个 $F_r(z)$ 都是 $m$ 个一次因子的乘积。但注意到：在一段较短的时间区间 $[l, R]$ 内，绝大多数弹珠的状态 $c_i$ 根本没有发生变化。

我们对事件下标区间 $[l, R]$（$1 \le l \le R \le nm - 1$）进行自底向上的分治：

• 活跃弹珠集合 $I_{l, R}$： 定义 $I_{l, R}$ 为在事件区间 $[l + 1, R]$ 内至少发生过一次状态变化的弹珠集合。
• 在区间 $[l, R]$ 内部（即对于所有的 $F_l, F_{l+1}, \dots, F_R$），任何不属于 $I_{l, R}$ 的弹珠 $i \notin I_{l, R}$，其状态 $c_i$ 保持恒定不变。
• 集合大小受区间长度与弹珠总数双重限制：$\vert{}I_{l, R}\vert{} \le \min(m, R - l)$。

• 分治状态定义： 将区间 $[l, R]$ 内所有不变的因子提取到括号外，仅维护由活跃弹珠构成的局部多项式（次数 $\le \vert{}I_{l, R}\vert{}$）：

$$H_{l, R}(z) = \sum_{r=l}^R w_r \prod_{i \in I_{l, R}} L_{c_i^{(r)}}(z)$$

• 分治合并转移：
• 递归基（$l = R$）：区间 $[l + 1, l]$ 为空，没有任何弹珠发生变化，故 $I_{l, l} = \emptyset$，局部多项式为 $0$ 次常数多项式：

$$H_{l, l}(z) = w_l$$

1. 合并左右子区间（$mid = \lfloor \frac{l + R}{2} \rfloor$）： 左半区间为 $[l, mid]$，右半区间为 $[mid + 1, R]$。跨越中点的第 $mid + 1$ 个事件会使弹珠 $i_{mid+1}$ 状态发生改变，因此：

$$I_{l, R} = I_{l, mid} \cup I_{mid+1, R} \cup \{i_{mid+1}\}$$

• 对于属于 $I_{l, R} \setminus I_{l, mid}$ 的弹珠，它们在左半区间 $[l, mid]$ 内状态恒定，等于 $mid$ 时刻的状态 $c_i^{(mid)}$；
• 对于属于 $I_{l, R} \setminus I_{mid+1, R}$ 的弹珠，它们在右半区间 $[mid + 1, R]$ 内状态恒定，等于 $mid + 1$ 时刻的状态 $c_i^{(mid+1)}$。

设补集乘积多项式分别为：

$$M_L(z) = \prod_{i \in I_{l, R} \setminus I_{l, mid}} L_{c_i^{(mid)}}(z), \qquad M_R(z) = \prod_{i \in I_{l, R} \setminus I_{mid+1, R}} L_{c_i^{(mid+1)}}(z)$$

则当前区间的局部多项式可以通过两次多项式乘法合并得到：

$$H_{l, R}(z) = H_{l, mid}(z) \cdot M_L(z) + H_{mid+1, R}(z) \cdot M_R(z)$$

（由于最终只需取到 $z^{k-1}$ 项，所有多项式在乘法后均可直接对 $z^k$ 取模截断。） 3. 根节点汇总： 分治到根节点 $[1, nm - 1]$ 后，若有从未出现在 $I_{1, nm-1}$ 中的弹珠（当 $n \ge 1$ 时所有弹珠均会变化，故 $I_{1, nm-1} = \{1, \dots, m\}$），将其因子乘入即可得到 $\Phi(z) = H_{1, nm-1}(z)$。

3. 复杂度分析

将分治树按区间长度 $L = R - l$ 与 $m$ 的大小关系分为两层剖析：

1. 底层子树（区间长度 $L < m$，共约 $n$ 棵规模为 $m$ 的子树）：
2. 在单棵规模为 $m$ 的子树中，设左、右补集为 $\Delta_L = I_{l, R} \setminus I_{l, mid}$ 与 $\Delta_R = I_{l, R} \setminus I_{mid+1, R}$。
3. 注意到 $\vert{}\Delta_L\vert{} \le \vert{}I_{mid+1, R}\vert{} + 1 \le \frac{L}{2} + 1$。在子树的每一层，所有节点的 $\vert{}I_{l, R}\vert{}$ 之和不超过 $m$，且 $\sum (\vert{}\Delta_L\vert{} + \vert{}\Delta_R\vert{}) \le m$。
4. 在每个节点上，用分治 NTT 计算一次因子乘积 $M_L(z)$ 和 $M_R(z)$ 耗时 $O(\vert{}\Delta\vert{} \log^2 \vert{}\Delta\vert{})$，再与 $H$ 做 NTT 乘法耗时 $O(\vert{}I_{l, R}\vert{} \log \vert{}I_{l, R}\vert{})$。
5. 单棵规模为 $m$ 的子树总耗时为 $O(m \log^3 m)$，$n$ 棵子树合计耗时 $O(nm \log^3 m)$。

1. 顶层节点（区间长度 $L \ge m$，整棵树中仅有 $O(n)$ 个此类节点）：
2. 由于 $\vert{}I_{l, R}\vert{} \le m$，所有多项式次数被严格限制在 $k = \frac{m+1}{2}$ 以内。
3. 甚至当区间足够大使得 $I_{l, mid} = I_{mid+1, R} = \{1, \dots, m\}$ 时，补集 $\Delta_L = \Delta_R = \emptyset$，此时 $M_L(z) = M_R(z) = 1$，合并退化为 $O(m)$ 的多项式直接相加。
4. 顶层共 $O(n)$ 个节点，总耗时不超过 $O(nm \log^2 m)$。

1. 空间复杂度优化（分段处理）：
2. 若直接对 $[1, nm - 1]$ 建分治树，空间复杂度为 $O(nm)$。
3. 若将 $nm$ 个事件按每块大小 $m$ 切分为 $n$ 个块，结合优先队列多路归并逐块生成事件，对每个块独立跑一次规模为 $m$ 的分治 NTT 并累加至 $\Phi(z)$，则空间复杂度可进一步压缩至 $O(n + m \log m)$。