No.206

大きさが $N$ で $A_i$ 番目のビットを立てた BitArray を作る. $B_i$ も同様にして作る.

あとは $B_i$ の BitArray を1ビットずつずらしながら $A_i$ の BitArray との AND を取り, 立っているビット数を数える.

ビットシフト, AND 演算, popcnt を駆使して定数倍高速化で間に合う.

別解:

$$f(x) = \sum_i x^{A_i} \\ g(x) = \sum_j x^{N-B_j}$$

とすると,

$$h(x) = f(x)g(x) = \sum_i a_i \cdot x^i$$

の $a_{N+v}$ は, $A_i + (N - B_j) = N + v$ となる $i, j$ の組み合わせの数である.

$$A_i + (N - B_j) = N + v \ \Rightarrow \ A_i = B_j + v$$

であるから, $a_i$ が $v$ ずらしたときの積集合の数となる.

よって, $h(x) = f(x)g(x)$ を FFT で計算すればいい.