Asterism Stream 题解

思路

设 $F(x)$ 为当前数是 $x$ 时到达 $[n,+\infty)$ 还需的期望步数，令 $k=1/2$，则

$$F(x)=0\ (x\ge n),\qquad F(x)=1+kF(x+1)+kF(2x)\ (x<n).$$

小档可显式展开两棵操作分支；中档从 $n-1$ 到 $1$ 逆序计算全部状态。

做法

满档把一段上的函数写成若干几何项 $a k^{bx}$ 的和。从已知区间 $[2l,2r]$ 缩到 $[l,r]$ 时，展开连续的 $F(x+1)$ 转移，可得

$$F(x)=k^{r-x+1}F(r+1)+\sum_{i=0}^{r-x}k^{i+1}F(2x+2i)+\sum_{i=0}^{r-x}k^i.$$

将旧表示中的每个 $a k^{bx}$ 代入中间求和，有限几何级数只会产生指数 $-1$ 与 $2b$ 两类新项；相同指数合并。因此每缩小一半区间，几何项数量只增加常数。初始 $[n,2n]$ 上函数恒为零，连续缩小到位置 $1$ 后直接代入求值。

标准解按指数 $-2^i$ 存系数；独立满分解用“指数到系数”的有序映射实现同一代数递推。

复杂度

显式操作树为指数复杂度，线性 DP 为 $O(n)$。满分算法每层有 $O(\log n)$ 个几何项，每项进行模幂，时间复杂度 $O(\log^3 n)$，空间复杂度 $O(\log n)$。