概要 整数Lが与えられる。下記の条件を満たす非負整数の組(a, b)がいくつあるかを求めよ。(mod 10^9+7 して出力) a+b ≦ L a+b = a xor b 制約 1 ≦ L 方針 a + b = a xor b ⇔ a & b = 0 ⇔ a, bの2進表記でどちらも1となる桁がない（繰り上がりがない）下記の…

令和ABC初回。残念ながらunratedでした。F - XOR Matching 概要 整数M, Kが与えられる。長さが2^(M+1)の数列aで下記を満たす数列が構築できる場合、その数列を1つ出力せよ。できない場合-1を出力せよ。 要素に0, 0, 1, 1, ... 2^M, 2^Mをもつ a[i] = a[j] と…

E - Enumerate Xor Sum 概要 長さNの数列Aが与えられる。i=1, …, Nについて(A1 xor X) + (A2 xor X) + … (Ai xor X)を出力せよ。ただし、X = A1 xor A2 xor … xor Aiとする。 制約 1 ≦ N ≦ 3 * 10^5 0 ≦ Ai 方針 2進けたごとにみていくとうまくいく。各2進け…

E - Exclusive OR Queries 概要 長さNの数列Aがある。Q個のクエリが与えられるので、それに解答せよ。 i番目のクエリではLi, Ri, Xiが与えられる。AのうちLi以上Ri以下のすべての項のXORを答えよ。またその後、Li以上Ri以下のすべての項をXiにする。 制約 1 …