概要

最適に操作を行ったときのコストを考え，畳み込みを用いて高速化します．

問題原案：uni_kakurenbo

解説

添え字は 0-based indexing として表現します．

まずはクエリ毎に考えてみましょう．
回文を目指すので，考えるべきは $B_i$ と $B_{k-i-1}$ とのペアのみについてのコストの最小化です．

$B_i = B_{k-i-1}$ とするために必要なコストの最小値を考えましょう．

$x = B_i, \, y = B_{k-i-1}$ とします．
今できることは $x \, |\!= p$ および $y \, |\!= p$ という $x, y$ の好きな「ビットを立てる」操作です．

操作によって既に立っているビットを下げることはできず，また既に立っているビットを「もう一度立てる」ことは完全な無駄(コストだけを消費して変更を加えない)です．

したがって，$x, y$ からそれぞれ「立てるべきビット」を選び，そのビットのみに注目して操作を行えばよいです．
$x = y$ とすることが目標ですから，$x$ のうち立てるべきビットは「$x$ で立っておらず，かつ $y$ で立っている」ビット，すなわち $p = \tilde{x} \,\&\, y$ として操作をするのが最適です．同様に $y$ のうち立てるべきビットは「$y$ で立っておらず，かつ $x$ で立っている」ビット，すなわち $p = x \,\&\, \tilde{y}$ が最適です．($2$ 非負整数 $u, v$ に対して $\tilde{u}$ は $u$ の bitwise NOT，$u \,\&\, v$ は $u, v$ の bitwise AND．)

したがって，$x = y$ とするために必要なコストの最小値は $\tilde{x} \,\&\, y + x \,\&\, \tilde{y}$ であるとわかりました．

これを少し整理します．

• $\tilde{x} \,\&\, y + x \,\&\, \tilde{y} \\ = (\tilde{x} \,\&\, y) \,|\, (x \,\&\, \tilde{y}) + (\tilde{x} \,\&\, y) \,\&\, (x \,\&\, \tilde{y}) \\ = (\tilde{x} \,\&\, y) \,|\, (x \,\&\, \tilde{y}) + (x \,\&\, \tilde{x}) \,\&\, (y \,\&\, \tilde{y}) \\ = (\tilde{x} \,\&\, y) \,|\, (x \,\&\, \tilde{y}) + 0 \,\&\, 0 \\ = (\tilde{x} \,\&\, y) \,|\, (x \,\&\, \tilde{y}) \\ = x \oplus y \;$ ($2$ 非負整数 $u, v$ に対して $u \oplus v$ は $u, v$ の bitwise XOR．)

となります．

以上から，この問題の答えは次のように表せることがわかりました：

• $\displaystyle \frac{1}{2}\sum_{0 \leq i < k} B_i \oplus B_{k-i-1}$

これはビットごとに独立して考えられるので，非負整数 $u$ の $b$ bit 目を $u^{(b)}$ と表すことにすると，以下のような変形ができます：

• $\displaystyle \sum_{0 \leq i < k} B_i \oplus B_{k-i-1} \\ = \displaystyle \sum_{0 \leq i < k} \; \sum_{0 \leq b < 30} 2^b \left(B_i^{(b)} \oplus B_{k-i-1}^{(b)}\right) \\ = \sum_{0 \leq b < 30} \; 2^b \left( \sum_{0 \leq i < k} B_i^{(b)} \oplus B_{k-i-1}^{(b)} \right)$

一度 $k, b$ を固定し，$\displaystyle \sum_{0 \leq i < k} B_i^{(b)} \; \oplus\; B_{k-i-1}^{(b)}$ の値を高速に求めることを考えます．

任意の $2$ 非負整数 $u, v$ について $u \oplus v = u + v - 2\,(u \,\&\, v)$ が成り立つので， $u, v \in \, \{\, 0, 1 \,\}$ のとき，$u \oplus v = u + v - 2 u v$ です．

したがって，

• $\displaystyle \sum_{0 \leq i < k} B_i^{(b)} \oplus B_{k-i-1}^{(b)} \\ = \sum_{0 \leq i < k} \left(B_i^{(b)} + B_{k-i-1}^{(b)} - 2 \, B_i^{(b)} B_{k-i-1}^{(b)}\right) \\ = \sum_{0 \leq i < k} \left(B_i^{(b)} + B_{i}^{(b)} - 2 \, B_i^{(b)} B_{k-i-1}^{(b)}\right) \\ = \sum_{0 \leq i < k} \left(2 \, B_{i}^{(b)} - 2 \, B_i^{(b)} B_{k-i-1}^{(b)}\right) \\ = 2 \sum_{0 \leq i < k} \left(B_i^{(b)} - B_i^{(b)} B_{k-i-1}^{(b)}\right) \\ = 2 \left( \sum_{0 \leq i < k} B_i^{(b)} - \sum_{0 \leq i < k} B_i^{(b)} B_{k-i-1} ^ {(b)} \right)$

と変形できました．

ここで $\displaystyle \sum_{0 \leq i < k} B_i^{(b)} B_{k-i-1}^ {(b)}$ は「畳み込み」を用いることで，$b$ を固定したときの各の $k$ に対した値をまとめて高速に求めることができます．(C++ の ACL では atcoder::convolution が利用できます．Python ならば numpy などを用いるとよいでしょう．)

また，$\displaystyle \sum_{0 \leq i < k} B_i^{(b)}$ については累積和を用いることで，$b$ を固定したときの各 $k$ に対して高速化できます．

おまけ：定数倍の高速化

上記で述べたことを (畳み込みのライブラリを用いるなどして) 愚直に実装すると， $A < 2^{10}$ という制約から離散フーリエ変換とその逆変換を合わせて最大 $10 \times 3 = 30$ 回行うことになります．

ここでは等しい列同士の合成積を求めたいということと，離散フーリエ変換とその逆変換が線形な演算であることを利用すると，$10$ 回の離散フーリエ変換を行って得られたそれぞれの列に対して (畳み込みのための) 適当な操作を施し，さらにそれらに累積和の項の加算や $2^b$ の定数倍の乗算を行ったものを $10$ ビット分合計し，最後にまとめて離散フーリエ変換の逆変換を $1$ 回行うことで，全体で最大 $11$ 回(約1/3)に離散フーリエ変換とその逆変換の合計回数を減らすことができます．(下記の実装例ではこちらを採用しています．)

C++ の ACL では atcoder::internal::butterfly および atcoder::internal::butterfly_inv が利用できます．(atcoder::internal 名前空間内の関数等の仕様は保証されていないので注意してください．)

なお $A \times N < 2^{10} \times (5 \times 10^5) < 998244353$ であるので $\mathbb{F}_{998244353}$ 上で計算を行っても問題なく正しい答えが得られることが分かります．

解説：uni_kakurenbo

実装例