XiaJiaFeng さんのコードが何をしているのかの解説です。 参考コード

関数 \(\mathrm{mask}, f\) を 以下のように定義します。

• \(\mathrm{mask}(a) : (a \;\mathrm{OR}\; s_{i}) = a\) を 満たす \(i\) の数
• \(f(l, r) : x = l\) から始めて、ちょうど \(x = r\) とする方法の場合の数

出力すべき値は \(f(0, 2^{N})\) です。

\(f(l, r)\) を再帰的に求めることを考えます。

\(l + 1 = r \) のとき

\(x = x + 1\) にするには、\((x \;\mathrm{OR}\; s_{i}) = x\) を満たす \(s_{i}\) を選ぶしかないので、\(f(l, r) = \mathrm{mask}(l)\) が成り立ちます。

\(l + 2^{d + 1} = r\) かつ \(l\) の \(d\) 桁目の bit が \(0\) のとき \((0\leq d)\)

\(L := f(l, l + 2^{d})\)

\(R := f(l + 2^{d}, r)\)

\(L, R\) を上記のように定義します。

\(x = l\) から始めて \(x = r\) にする方法は以下の \(2\) 通りあります。

• \(x = l + 2^{d}\) を経由する方法
• \(x = l + 2^{d}\) を経由しない方法

\(x = l + 2^{d}\) を経由する方法は、\(LR\) 通りあります。

\(x = l + 2^{d}\) を経由しない方法は \(x = l + 2^{d}\) から \(x = r\) にする方法から、途中で選んだ \(s_{i}\) がどれも \(d\) 桁目が \(0\) のものを引いた値です。これは \(f\) の定義から \((R - L)\) と表せます。

よって、\(f(l, r) = LR + R - L\) です。

上記の事実を用いるとこの問題を \(O(N 2^{N} + M)\) で解くことができます。\(f(0, 2^{N})\) を求める部分の計算量は、公式解説などと異なり \(O(2^{N})\) で、\(\mathrm{mask}\) を求めるために高速ゼータ変換する部分がボトルネックです。

自分(potato167) の実装 c++

自分(potato167) の実装 python