次のような 2 変数関数 \(f(x,y), g(x,y)\) を考えます。

\[f(x,y) = \sum_{i=0}^{2^N-1} A_i x^i y^{\text{popcount}(i)}\]

\[g(x,y) = \sum_{i=0}^{2^N-1} B_i x^i y^{\text{popcount}(i)}\]

ただし、\(y\) のべき同士の積は通常の積なのに対して \(x\) のべき同士の積は指数の bitwise or になるものとします。すなわち、

\[x^a \times x^b = x^{a \vert b}, y^a \times y^b = y^{a+b}\]

が成り立っているとします。

このような \(f, g\) を利用すると、\(f\) と \(g\) の積 \(fg\) が求まれば元の問題を解くことができます。
\(fg\) は 2 次元 FFT の要領で計算できます。すなわち、\(x\) 軸方向に subset zeta transform を計算した後に \(y\) 軸方向で通常の畳み込みを行い、その後 inverse subset zeta transform で復元すればよいです。計算量は \(\mathrm{O}(Q + 2^N N^2)\) で、これは十分高速です。