概要
長さ $N$ の数列 $A_i$ が与えられる。以下を満たす $(l, r)$ の組の数を求めよ。 ここで、 $\oplus$ は bitwise xor を表す。
$$ A_l + A_{l + 1} + \cdots + A_r = A_l \oplus A_{l + 1} \oplus \cdots \oplus A_r $$
制約
- $1 \leq N \leq 2 \times 10^5$
- $0 \leq A_i \leq 2^{20}$
解説
まず、和と xor の間には、以下の恒等式が成り立つ。 ここで、 $\land$ は bitwise and を表す。
$$ A + B = A \oplus B + 2(A \land B) $$
この恒等式から、以下が成り立つ。
$$ \begin{aligned} A \land B = 0 &\implies A + B = A \oplus B \\ A \land B \neq 0 &\implies A + B \gt A \oplus B \end{aligned} $$
これを拡張すると、以下が成り立つ。
$$ \begin{aligned} & A_l + A_{l + 1} + \cdots + A_r = A_l \oplus A_{l + 1} \oplus \cdots \oplus A_r \\ \iff& A_l \land A_{l + 1} \land \cdots \land A_r = 0 \end{aligned} $$
後は、これを満たす $(l, r)$ を数え上げればいい。
$l$ を固定したとき、and の性質から上の条件は $r$ について単調性を持つ。 すなわち、「 $l\leq r \leq r_0$ なら常に $(l, r)$ は条件を満たし、逆に $r \gt r_0$ なら常に $(l, r)$ は条件を満たさない」という境界値 $r_0$ が存在する。このとき条件を満たす組の数は $r_0 - l + 1$ 個となる。これを各 $1 \leq l \leq N$ について全部求めて、足し合わせればいい。 この $r_0$ は尺取り法なら $O(N)$、二分探索なら $O(N \log N)$ で全て求められる。
なお $(l, r)$ が条件を満たすかの判定は、問題文通りに累積和と累積 xor を使って判定するといい。 and は不可逆なので、累積 and は使えない。
実装例
答えの最大値は $10^{10}$ 程度になるため、地味に int ではオーバーフローすることに注意(1 敗)。
提出 #34713207 - AtCoder Regular Contest 098
|
|