平衡码题解

思路

先求前缀函数 $F(x)$：区间 $[0,x]$ 中数位和为偶数的整数个数。答案就是 $F(r)-F(l-1)$。

用数位 DP 从高位到低位处理 $x$。状态只需记录已经选择的数字之和奇偶性，以及当前前缀是否仍与 $x$ 相等。枚举下一位数字并更新奇偶性；所有位处理完后，只累加偶数状态。前导零不改变数位和，因此自然包含整数 $0$。

做法

1. 把 $x$ 转成十进制数字序列。
2. 维护受限前缀的奇偶性，并用两个计数保存已经小于 $x$ 的前缀在两种奇偶状态下的方案数。
3. 对每一位枚举比当前上界小的数字加入自由状态，再沿等于上界的数字继续。
4. 处理完所有位后，若受限前缀为偶数则再计入它本身。
5. 对每个询问输出 $F(r)-F(l-1)$。

证明

每个 $0\le y\le x$ 的定长十进制表示在第一处小于 $x$ 的位置唯一进入自由状态；若始终相等，则对应 $y=x$。DP 对每个位置枚举的数字恰好累加其奇偶贡献，因此所有 $y$ 被不重不漏地分类到最终的奇偶状态。偶数状态的方案数正是 $F(x)$。两个前缀相减后恰好保留 $[l,r]$，所以算法正确。

复杂度

每个前缀只处理至多 19 位，每位枚举 10 个数字。每组数据时间复杂度为 $O(190)$，额外空间复杂度为 $O(1)$。