形式的べき級数で考えると、求めるべき値は

\[ \sum_{i=1}^{N} \sum_{j=1}^M [x^{b_j}] (1 + x)^{a_i} \]

であり、特に\(f(x) = \sum_{i=1}^N (1 + x)^{a_i}\) とおくと、

\[ \sum_{j=1}^M [x^{b_j}] f(x) \]

です。ここで、\(g(x) = \sum_{i=1}^{N} x^{a_i}\) とすると、\(f(x) = g(x+1)\) であり、これは Polynomial Taylor Shift と言われる手法で\(f(x)\) の係数を得ることができます。 （Polynomial Taylor Shiftについては、例えばABC215-Gの解説などを参照してください。）

\(f(x)\) の係数を求めて、各 \(b_j\) に対応する係数の値の総和を取ることでこの問題を解くことができます。

実装例(C++) （Nyaan’s Libraryを使用しています。）