定義

まず \(P\) を十分大きな素数とします。

\(0\leq i \leq \max(A) + \lceil\log_{2}(N)\rceil\) に対して、\(z_{i}\) を適当に生成した乱数とします。

非負整数 \(x\) に対して、\(\mathrm{bit}(x)\) を非負整数からなる集合 \(S\) であって、\(\displaystyle x = \sum_{d \in S} 2^{d}\) を満たすものとします。

\(\mathrm{hash}(x)\) を \(\displaystyle x = \sum_{d \in \mathrm{bit}(S)} z_{d}\) を \(P\) で割ったあまりと定義します。

補題

\(L < M < R\) に対して以下の補題を解くことを考えます。

• \(L \leq l < M \leq r < R\) を満たす \((l, r)\) であって、\(\displaystyle \sum_{i = l}^{r} 2^{A_{i}}\) が \(2\) べきであるような \((l, r)\) の組は何通りですか

\(L \leq l < M\) に対して、\(X_{l} = \displaystyle \sum_{i = l}^{M - 1} 2^{A_{i}}\) とし、\(M\leq r < R\) に対して、\(Y_{r} = \displaystyle \sum_{i = M}^{r} 2^{A_{i}}\) としたとき、\(X_{l} + Y_{r}\) が \(2\) べきであるような \((l, r)\) が何通りかわかればいいです。

まず、任意の \(X_{l}, Y_{r}\) に対して、以下の値を求めます。

• \(\mathrm{hash}(X_{l})\)
• \(\max(\mathrm{bit}(X_{l}))\)
• \(\min(\mathrm{bit}(X_{l}))\)

これらの値は \(X_{M - 1}, X_{M - 2}, \dots , X_{L}\) の順に \(\mathrm{bit}(X_{l})\) を std::set などで管理すれば求められます。\(Y_{r}\) についても同様です。

次に、\(X_{l}, Y_{r}\) の大小で場合分けします。

\(X_{l} > Y_{r}\) であるとき

\(X_{l}\) を固定すると \(Y_{r}\) は一意に定まります。

つまり、\(Y_{r} = 2^{\max(\mathrm{bit}(X_{l})) + 1} - X_{l}\) となるような \(Y_{r}\) が存在するかどうかを判定すれば良いです。ここで、以下の式が成り立ちます。

\(\mathrm{hash}(2^{\max(\mathrm{bit}(X_{l})) + 1} - X_{l}) = \mathrm{hash}(2^{\max(\mathrm{bit}(X_{l})) + 1} - 1) - \mathrm{hash}(X_{l}) + \mathrm{hash}(2^{\min(\mathrm{bit}(X_{l}))}) - \mathrm{hash}(2^{\min(\mathrm{bit}(X_{l}))})\)

よって、上記の式の値を求めて、それと \(\mathrm{hash}(Y_{r})\) が一致しているような \(r\) が存在するか判定すれば良いです。

ただし、\(X_{l}\) が \(2\) べきであるときはそのような \(Y_{r}\) は存在しません。

\(X_{l} = Y_{r}\) であるとき

\(\max(\mathrm{bit}(X_{l})) = \min(\mathrm{bit}(X_{l})) = \max(\mathrm{bit}(Y_{r})) = \min(\mathrm{bit}(Y_{r}))\) となるような \((l, r)\) の組がもとまればいいです。

以上で補題を解くことができました。

計算量

以上を分割統治すれば時間計算量 \(O(N\log^{2}(N))\) で解くことができます。

上の補題では \(l \neq r\) の場合を網羅しているので、補題の答えの総和に \(N\) を足したものが答えになります。

実装例

std::set の代わりに Fast Set を用いています。

c++ 466 ms