coincidence - abc 138 f - tac

#桁dp #xor

mod → 大小関係を見る
を適用.

余りは y で, xor は y ^ x.

y % x = y ^ x (与えられた式)
y = x ^ y
0 ^ y = x ^ y
x = 0
制約より不可 (そもそも x ≤ y が制約).

y % x = y ^ x (与えられた式)
0 = 0
常に ok.

y % x = y ^ x になりえない.
まず, y ^ x の最上位桁は 1.
y % x < x より, y % x の最上位桁は 0.

x < y < 2x より y / x = 1.
y = y (+ x - x) = x + (y - x)
より,
y % x = y - x (ポイント !!)

y % x = y ^ x
y - x = y + x - 2 * (y & x)

x = y & x

y = 1 1 0 1 0 とすると,
x = ? ? 0 ? 0

0
1
だけ禁止.

ただし, 桁数は同じ.
(先頭は 1 1)

あと, L ≤ x ≤ y ≤ R
L ≤ x, y ≤ Rを判定すればいい

dp[i][j][k][l]
i : 桁 0 ~ 60
j : 0, 1 → L ≤ xをすでに満たしているか or 今のところ一致.
k : 0, 1 → y ≤ R を...
l : 先頭 bit (1 1) がすでに現れたか.

j に関して具体例.
L = 1011 とする.
x = 0... はだめ (x < L).
x = 10... は今のところ一致 (L = x).
x = 11... はすでに L ≤ x を満たしてるからあとはなんでもok.

補足.
x < y の場合, x = 0 しかない他の説明.
y ^ x = (y + x) - 2(y & x) より,
y % x = y ^ x (与えられた式)
y = (y + x) - 2(y & x)
x = 2(y & x) (x は偶数)
y & x = x / 2

y & x が x を右に 1 つシフトしたものに等しい.
x は 0 でない偶数なので, 最下位桁でない桁に 1 がある.
一番右の 1 の右隣は 0 なので, x & y $\neq$ x / 2.