Asterism

给定一变量，初始为 \(1\)，每次等概率随机进行以下两种操作之一： 令 \(x\) 加一。 令 \(x\) 乘二。 求期望多少次操作之后 \(x\) 会 \(\ge n\)。 \(T\) 组数据，\(T\le 100\)，\(n\le 10^{18}\)。 对着 aw 老师的题解学的，感觉太深刻。 ......

首先讲点正常想的到的做法。 首先转化成：计数 * + * + * * + * * 的序列，要求在序列最后一个操作后恰好 \(\ge n\)，每个序列的贡献是 \(\frac{1}{2^{len}}\)。 枚举总共有多少个 *；枚举最后一个 + 之后有多少个 *。 这样，最后一个 + 的贡献是确定的， ......

洛谷传送门 CF 传送门 好题。 考虑计算 \(x\) 落在 \([1, n - 1]\) 的概率。设 \(f_i\) 为 \(x\) 经过 \(i\) 的概率，答案即为 \(\sum\limits_{i = 1}^{n - 1} f_i\)。 \(f\) 有一个朴素的递推： \[f_i = \be ......

### 题意 给定一个 $n$ ， 有一个初始为 $1$ 的整数 $x$ ， 每次有相同概率进行以下两个操作的其中一种： - 使 $x$ 加 $1$ - 使 $x$ 乘 $2$ 问期望多少步操作可以使 $x$ 大于 $n$ ， 输出期望步数模 $998244353$ 的值。 其中 $1 \leq n ......