求める値は、 \(S=\sum_{i=1}^N(1+x)^{A_i}\) として \(\sum_{i=1}^MS[x^{B_i}]\) となります。よって、 \(S\) を高速に計算できればよいです。

ある \(A\) に対する答えを \(S(A)\) とし、これを再帰的に求めます。閾値 \(m\) を定め、 \(A\) の要素のうち \(m\) 以上のものから \(m\) を引いたものの列 \(A_1\) 、そうでないものの列を \(A_2\) とします。このとき、 \(S(A)=(1+x)^mS(A_1)+S(A_2)\) となります。

ここで、 \((1+x)^m\) は二項係数の列挙、 \((1+x)^mS(A_1)\) は畳み込みを使って計算できます。

分割統治を行うことで、要素の最大値を \(K\) として \(O(N+M+K(\log K)^2)\) で解くことができます。