AT_abc138_f [ABC138F] Coincidence
_Yonder_
·
·
题解
遇到这种题，首先要狠狠地♡推性质。
模运算其实就是多次的减运算，则有：
当 y<2x 时，y\bmod x=y-x。
当 y\ge2x 时，y\bmod x<y-x。
因为 y-x\le x\oplus y，所以只有 y<2x 的情况下可能有解。
因为 y-x=x\oplus y,y<2x，所以 x,y 二进制下位数相同。
手推不难发现：
当 y 的第 i 位为 1，x 的第 i 位为 0/1。
当 y 的第 i 位为 0，x 的第 i 位为 0。
数位 dp 即可，状态设计：f_{i,l,r,w}，i 表示二进制的第 i 位，l 表示是否需要大于 L 的第 i 位，r 表示是否需要小于 R 的第 i 位，w 表示 i\sim 64 位是否都为 0。