(略解です。正式な解説は後日公開されます。)

色々な解法がある。例えば \(L = \left\lceil \log \max(A) \right\rceil \leq 24\) として \(\mathrm{O}(N 1.415^L)\) 解法が何種類か存在していずれも定数倍が良好であれば通ることを確認している。
ここでは期待計算量が \(\mathrm{O}\left(N {1.334}^L\right)\) である解法を説明する。

おおよそ以下の問題を解けばよい。

以下の \(2\) 種類のクエリを \(N\) 回処理せよ。

• add クエリ：長さ \(L\) の \(01?\) 列が与えられるのでマッチする index \(i\) それぞれに \(dp[i] += x\)
• get クエリ：長さ \(L\) の \(01?\) 列 \(i\) が与えられるので \(dp[i]\) を出力

各 bit 毎に以下の 3 個の戦略のいずれかを取ることを考える。

(1) 直接書く：? が来るごとに 0, 1 にそれぞれ寄与を加算する
(2) 0 で包除 ：0, ? で正規化, add 1 が来たら dp[?]+=1, dp[0] -= 1 とする
(3) 1 で包除 ：1, ? で正規化, add 0 が来たら dp[?]+= 1, dp[1] -= 1 とする

各戦略ごとのコストをまとめた表が以下となる。

いずれの列も和が \(4\) となっている点がポイントで、これを利用して各 bit 毎に \(3\) 個の戦略を乱択することにすると各 bit の計算量への寄与は \(\frac{4}{3}\) となるため \(1\) 回の操作の期待値が \(\mathrm{O}\left(1.334^L\right)\) となる。