\(dp[k],dp2[k],a_i,b_i\) を以下のように定義します。

• \(dp[k]\)：操作が終了した段階で \(x = k\) となっている操作列の個数
• \(dp2[k]\)：操作列と \(i\) の組であって、\((x | s_i) = k\) となるものの個数
• \(a_i\)：\(s_j = i\) を満たす \(j\) の個数

\(a,b\) はあらかじめ計算しておくと、以下のように更新を行うことが出来ます。

• \(dp[k] = dp2[k-1]\)
• \(dp2[k] = \sum_{i | j = k} a_i dp[j] = (\sum_{i \subset k} a_i)(\sum_{j \subset k} dp[j]) - (\sum_{j \subsetneq k} dp2[j])\)

zeta 変換を用いることで \(dp,dp2\) の下位集合に対する累積和を計算したいところですが、\(dp,dp2\) の値は順番に決まっていくため予め zeta 変換を適用しておくなどといったことは出来ず、online で zeta 変換のようなことをする必要があります。具体的には、以下の問題が処理できれば上記の遷移も処理できます。

長さ $2^N$ の数列 $x=(x_0,x_1,\dots,x_{2^N-1})$ がある。始め、$x$ の要素は全て $0$ である。以下を $i = 0,1,\dots,2^N-1$ の順番にオンラインで処理せよ。

• $\sum_{j \subset i} x_j$ を求めて、$x_i$ に $v$ を加算する。

各クエリが来る度に、\(\sum_{j \subset i} x_j\) が高速に求まる必要があります。例えば、数列 \(y\) を以下の状態が常に満たされるように保持することにします。

• \(i\) に対するクエリを処理する直前の \(y\) は以下のような状態である。ただし、\(i= 2^{b_1} + 2^{b_2} + \dots + 2^{b_k},b_1 > b_2 > \dots > b_k,c_l = \sum_{j=1}^{l} 2^{b_j}\) とする。
  • \((y_{c_l},y_{c_l+1},\dots,y_{c_{l+1}-1})\) は \((x_{c_l},x_{c_l+1},\dots,x_{c_{l+1}-1})\) を zeta 変換したものと等しい。

この状態を保っていれば、\(\sum_{j \subset i} x_i = \sum_{l = 1}^{k} y_{i\ \mathrm{xor}\ 2^{b_l}}\) となるため \(\sum_{j \subset i} x_i\) を \(\mathrm{O}(N)\) 時間で求められます。また、\(y\) の更新も \(y_i = x_i\) とすることで \(b\) の末尾に \(0\) を追加した上で、\(b_{k-1} = b_k\) である間 \(2\) 個の列をマージすればよいです。マージは線形で可能なため計算量は償却 \(\mathrm{O}(N)\) となります。

よって、この問題を \(\mathrm{O}(2^N N)\) で解くことが出来ます。メモリを \(\mathrm{O}(2^N N)\) 取ってしまうと MLE するため気を付けましょう。(実際に zeta 変換をする際に登場する \(2^N N\) 個の値を全て管理しようとすると \(\mathrm{O}(2^N N)\) 時間で解くことが出来ますが、MLE します。)