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\)。
已完成
手机扫一扫
移动阅读更方便
你可能感兴趣的文章