2023-02-03
题目
翻译
难度&重要性(1~10):6
题目来源
AtCoder
题目算法
数位dp
解题思路
\(1.\) 当 \(2x\leq y\)，有\(y-x>y\% x\)；
\(2.\) 当 \(2x>y\)，有\(y-x=y\% x\)。
\(3.\) \(y\oplus x\geq y-x\)。
于是：
\(2x\leq y\) 时，不存在 \(y\oplus x=y\% x\)。
所以 \(2x>y\)，即 \(x\) 和 \(y\) 的位数相同，最高位同时为 \(1\)。
那么问题就转化成，求 \(y-x=y\oplus x\) 的 \((x,y)\) 的对数。
满足 \(y-x=y\oplus x\)，那么 \(y\) 二进制下为 \(1\)，\(x\) 为 \(0\) 或 \(1\)，\(y\) 二进制下为 \(0\)，\(x\) 必为 \(0\)。
考虑数位 \(dp\)，这种类型的数位 \(dp\) 不像常规的数位 \(dp\) ，用 \(0\sim r\) 的答案减去 \(0\sim l-1\) 的答案。
我们考虑枚举哪一位为最高位，然后 \(dp_{i,x1,x2}\)表示前 \(i\) 位，数的大小有没有达到下界 \(L\)，有没有达到上界 \(R\) 的方案数，转移时先枚举 \(y\)，再枚举 \(x\)。
完成状态
已完成