Linear Xor

ビット毎に考えます。考慮すべきビットの数を $K$ とします。 最大の項が $2^{60}$ 未満なので $K \leq 60$です。

以下の $4$ つは同値です。

• 答えの $2^k$ の位が $1$ になる
• $(a \gt\gt k) \& 1, ((a + b) \gt\gt k) \& 1, ... ((a + (n-1)b) \gt\gt k) \& 1$ のうち $1$ が奇数個ある
• $(a \gt\gt k), ((a + b) \gt\gt k), ... ((a + (n-1)b) \gt\gt k)$ のうち奇数が奇数個ある
• $(a \gt\gt k) +((a + b) \gt\gt k) + ... ((a + (n-1)b) \gt\gt k)$ が奇数

一番下の式はAtCoder Libraryにあるfloor_sum(公式ドキュメント https://atcoder.github.io/ac-library/document_ja/math.html )を使うと1回あたり $O(min(k, log_2b))$ で求められます。

$k = 0, 1, ...K-1$ について計算するとクエリあたり $O(K^2)$ で答えられます。