题目链接
题意
定义序列 $a$ 满足 $a_0=1,a_i=a_{i-1}+\text{popc}(a_{i-1})$，其中 $\text{popc}$ 表示二进制下 $1$ 的个数。给定 \(n\)，求出最小的 \(i\) 满足 \(a_i=n\)，或报告不存在。
\[1\le n\le 10^{18}
\]
数据范围巨大。我们考虑倍增。
令 \(f_{i,j,k}\) 表示 \(x\equiv j \pmod {2^i}\)，\(i\) 之上还有 \(k\) 个一。要多久能在 \(2^i\) 位上进一。
转移是简单的。我们发现一步最多跳 \(\log V\) 次，所以只需要维护 \(\le \log V\) 的 \(j\)。
复杂度 \(\mathcal O(\log^3n)\)。