Project Euler 811
Project Euler 811
题目
Bitwise Recursion
Let \(b(n)\) be the largest power of \(2\) that divides \(n\). For example \(b(24) = 8\).
Define the recursive function:
\[\begin{align*} \begin{split} A(0) &= 1\\ A(2n) &= 3A(n) + 5A\big(2n - b(n)\big) \qquad n \gt 0\\ A(2n+1) &= A(n) \end{split} \end{align*}\]
and let \(H(t,r) = A\big((2^t+1)^r\big)\).
You are given \(H(3,2) = A(81) = 636056\).
Find \(H(10^{14}+31,62)\). Give your answer modulo \(1\,000\,062\,031\).
解决方案
先从二进制结构理解递归。
若 \(n=2m+1\)，则\(A(2m+1)=A(m).\)这等价于把二进制末尾的最低位 \(1\) 删除（右移一位），因此这一操作不会引入任何系数，表示“删除一个尾部 \(1\) 只有 \(1\) 种方式”。
若 \(n=2m\)，则\(A(2m)=3A(m)+5A(2m-b(m)).\)记 \(m\) 的最低位 \(1\) 在第 \(q\) 位（从 \(0\) 开始计），即\(b(m)=2^q, m\equiv 2^q\pmod{2^{q+1}}.\)那么 \(2m\) 的最低位 \(1\) 在第 \(q+1\) 位；而\(2m-b(m)=2m-2^q\)会把第 \(q+1\) 位的那个 \(1\) “往右挪一格”到第 \(q\) 位（其余更高位不变）。例如 \[ m=3(11_2),q=0: 2m=6(110_2),2m-1=5(101_2), \] 可以看到最低位 \(1\) 从位置 \(1\) 移到了位置 \(0\)。
因此偶数递归可以理解为：当末尾出现一个 \(0\) 时，有两种处理方式：
- 直接删除这个尾部 \(0\)：贡献系数 \(3\)，状态变为 \(m\)；
- 让“最近的一个 \(1\)”跨过这个 \(0\) 向右移动一格：贡献系数 \(5\)，状态变为 \(2m-b(m)\)。
递归的线性组合系数 \(3\) 与 \(5\)，正对应这两类操作的“方式数”。
把 \(n\) 的二进制从高位到低位写成块状形式：
\[n=1\underbrace{00\dots 00}_{x_1}1\underbrace{00\dots 00}_{x_2}1\underbrace{\dots}_{\dots}1\underbrace{00\ldots 00}_{x_{k-1}}1\underbrace{00\ldots 00}_{x_k}\]
其中共有 \(k\) 个 \(1\)，第 \(i\) 块含有 \(x_i\) 个 \(0\)（允许 \(x_i=0\)）。可见，每一个 \(0\) 的“命运”只取决于它左侧有多少个 \(1\)。
- 如果某个 \(0\) 左侧有 \(i\) 个 \(1\)，那么它最多会被某个 \(1\) 向右跨越 \(i\) 次；
- 每次跨越都会产生系数 \(5\)，并且会让它左侧的 \(1\) 数量减少 \(1\)；
- 在跨越发生之前，它也可能被直接删除，产生系数 \(3\) 并终止。
据此定义 \(v_i\)表示“一个 \(0\)，其左侧有 \(i\) 个 \(1\)，最终被处理干净的总方式数”。
当左侧没有 \(1\) 时，这个 \(0\) 不可能再被跨越，只剩下“删除”这一类终局行为，因此设\(v_0=1\)作为边界（表示不再需要额外乘任何因子）。
当左侧有 \(i\ge 1\) 个 \(1\) 时，这个 \(0\) 的第一步只有两种可能：
- 删除：贡献 \(3\)，结束；
- 被最近的 \(1\) 跨越一次：贡献 \(5\)，此后它左侧只剩 \(i-1\) 个 \(1\)，贡献 \(v_{i-1}\)。
因此得到递推\(v_i = 3+5v_{i-1}(i\ge 1).\)等价写成
\[ v_{i+1}=5v_i+3, v_0=1, \]
在分块表示中，第 \(i\) 块的每一个 \(0\) 左侧恰好有 \(i\) 个 \(1\)，因此每个这样的 \(0\) 都贡献一个因子 \(v_i\)。
并且这些 \(0\) 的选择过程彼此独立：对某个 \(0\) 做“删除/跨越”的选择，只会改变它所处的相对位置层级（即左侧剩余的 \(1\) 数量），不会引入和其它 \(0\) 的耦合项；递归的线性系数也恰好体现为乘法计数。于是整串 \(0\) 的总贡献就是逐个相乘。因此得到闭式：
\[ A(n)=\prod_{i=1}^{k} v_i^{x_i}. \]
这一表达式把原本看似复杂的递归，完全转化为“读取二进制中每个 \(1\) 后面跟了多少个 \(0\)”。
现在我们需要计算\(n=(2^t+1)^r.\)用二项式展开\(\displaystyle{(2^t+1)^r=\sum_{i=0}^{r}\binom{r}{i}2^{ti}.}\)
实现中可以用“二进制进位展开”的方式统一处理：把 \(\dbinom{r}{i}\) 看成在指数 \(ti\) 处的一个整数系数，反复把系数拆成二进制位并向高位转移，直到所有系数都变成 \(0/1\)，此时所有出现的指数就是 \(1\) 比特的位置集合。
得到置位位置（从大到小）为\(m_1>m_2>\cdots>m_k\ge 0,\)令哨兵 \(m_{k+1}=-1\)，则块长度为\(x_i=m_i-m_{i+1}-1.\)随后按\(\displaystyle{A(n)=\prod_{i=1}^{k} v_i^{x_i}}\)直接计算即可。
代码
1 | from collections import defaultdict |