题解

核心算法

先递归处理 n/2，返回后输出 n%2。

思路推导

高位来自更深层的递归，回溯时按高位到低位输出。

正确性说明

按照上述状态含义与转移顺序，每一步只使用已经正确求出的子问题；所有合法情况被完整计入，且互斥分类不会重复计数，因此最终输出即为题目所求。

复杂度

• 时间复杂度：O(log n)
• 空间复杂度：O(log n)

易错点

必须单独处理 n=0；递归调用应发生在输出当前余数之前。

完整标程见 std/main.cpp。