Math Division 详细题解

题目分析

核心题意

给定一个二进制表示的正整数 $x$（长度为 $n$，最高位为 $1$），每次操作可以等概率选择两种操作之一：

1. 向下取整除以 $2$：$x \leftarrow \lfloor \frac{x}{2} \rfloor$
2. 向上取整除以 $2$：$x \leftarrow \lceil \frac{x}{2} \rceil$

操作直到 $x=1$ 停止，求操作次数的数学期望，答案对 $10^9+7$ 取模（分数取模需计算乘法逆元）。

关键观察

1. 二进制长度为 $n$ 的数，纯向下取整操作到 $1$ 的固定次数是 $\boldsymbol{n-1}$ 次（比如 $110_{(2)}=6$，长度 $3$，纯向下操作：$6\to3\to1$，共 $2=3-1$ 次）。
2. 二进制中末尾的 $1$ 会额外增加操作次数的期望，这是唯一影响期望的变量。

---

数学推导

定义

设：

• $E(x)$：数字 $x$ 操作到 $1$ 的期望次数
• 模：$MOD=10^9+7$，$\frac{1}{2}$ 的模逆元 $\boldsymbol{inv2=500000004}$（因为 $2 \times 500000004 \equiv 1 \pmod{10^9+7}$）

递推公式

对任意 $x>1$：

$$E(x) = 1 + \frac{1}{2}E\left(\lfloor \frac{x}{2} \rfloor\right) + \frac{1}{2}E\left(\lceil \frac{x}{2} \rceil\right) $$

解释：当前操作计数 $1$ + 两种操作的期望平均。

二进制特性简化

将 $x$ 写成二进制：

• 若 $x$ 是偶数（最低位为 $0$）：$\lfloor \frac{x}{2} \rfloor = \lceil \frac{x}{2} \rceil$，此时 $E(x)=1+E(\frac{x}{2})$，无额外期望。
• 若 $x$ 是奇数（最低位为 $1$）：$\lceil \frac{x}{2} \rceil = \lfloor \frac{x}{2} \rfloor +1$，推导得：$$E(x) = E(\lfloor \frac{x}{2} \rfloor) + 2$$ 奇数会固定多 $1$ 次期望操作。

最终结论

1. 基础操作次数：$\boldsymbol{n-1}$（二进制长度减一）。
2. 额外期望：从最低位到次高位，每遇到一个 $1$，就累加 $\boldsymbol{\frac{1}{2^k}}$（$k$ 是该位到最低位的距离）。
3. 总期望：

$$\boldsymbol{答案 = (n-1) + \sum_{i=2}^{n} (s[i]=='1') \cdot \frac{1}{2^{n-i+1}}} $$

（$s[i]$ 是二进制字符串第 $i$ 位，下标从 $1$ 开始）

---

标程代码解析

核心代码逻辑

// 初始化答案为 0
ll ans = 0;
// 从二进制最低位（最后一位）遍历到次高位
for (ll i = n;i > 1;i -= 1) 
    // 遇到 1 就加 1，然后乘以 1/2（模逆元）
    ans = (ans + (s[i] == '1')) * inv2 % mod;
// 总答案 = 基础次数 + 额外期望
printf("%lld\n",(n - 1 + ans) % mod);

逐行解释

1. 遍历方向：从二进制最后一位（最低位）到第二位（次高位），最高位永远是 $1$ 且不影响额外期望。
2. 累加规则：
   • 每一位是 $1$，先 $+1$；
   • 然后整体 $\times \frac{1}{2}$（等价于 $\div 2$，模运算中用逆元实现）。
   • 这个过程自动实现了 $\frac{1}{2^k}$ 的求和（递推计算等比数列）。
3. 最终结果：基础次数 $n-1$ 加上额外期望 ans，取模输出。

---

样例验证（第一组样例）

输入：

3
110

• $n=3$，二进制串 $s[1]='1',s[2]='1',s[3]='0'$
• 基础次数：$3-1=2$
• 遍历计算 ans：
  1. $i=3$：$s[3]='0'$ → $ans=(0+0) \times inv2 = 0$
  2. $i=2$：$s[2]='1'$ → $ans=(0+1) \times inv2 = \frac{1}{2}$
• 总期望：$2 + \frac{1}{2} = \frac{5}{2}$
• 模运算：$\frac{5}{2} \equiv 5 \times 500000004 \equiv 500000006 \pmod{10^9+7}$，与样例输出一致。

---

模运算关键知识点

1. 分数取模：题目要求输出 $\frac{p}{q} \bmod MOD$，等价于 $p \times q^{-1} \bmod MOD$。
2. 逆元计算：$2$ 的逆元 $inv2=500000004$，是固定常量。
3. 取模规则：每一步运算都取模，防止溢出。

---

复杂度分析

• 时间复杂度：$\boldsymbol{O(\sum n)}$，所有测试 case 总长度不超过 $10^5$，符合时间限制。
• 空间复杂度：$\boldsymbol{O(n)}$，存储二进制字符串。

---

总结

1. 核心规律：二进制长度决定基础操作次数 $n-1$，低位的 $1$ 带来额外期望。
2. 计算技巧：逆序遍历 + 递推乘 $\frac{1}{2}$，高效计算额外期望和。
3. 模运算：分数取模使用乘法逆元，固定 $inv2=500000004$。