Let \(\displaystyle c_i = \sum_{j=1}^M \binom{A_i}{B_j}\) be the contribution of the \(i\)-th term of the outer summation.

Expanding this:

\[ \displaystyle c_i = \sum_{j=1}^M \begin{cases} {\dfrac {A_i!} {B_j! (A_i - B_j)!}} & \text{if } A_i \ge B_j \\[10pt] 0 & \text{if } A_i < B_j \end{cases}\]

If we define \(d_k\) to be the number of elements of \(B\) where \(B_i = k\), we can rewrite this as:

\[ \displaystyle \begin{array}{rl} c_i &\hspace{-7pt}= \displaystyle \sum_{k=0}^{A_i} \frac {d_k \cdot A_i!} {k! (A_i - k)!} \\ &\hspace{-7pt}= \displaystyle A_i! \cdot [x^{A_i}] \left( \sum_{k=0}^\infty \frac{d_k x^k}{k!} \right) \left( \sum_{k=0}^\infty \frac{x^k}{k!} \right) \end{array} \]

with the latter factor meaning “extract the coefficient of \(x^{A_i}\) of the product of these formal power series”.

Let \(K = \max _i A_i \,\). We may obtain coefficients \(0\) through \(K\) of \(\displaystyle \left( \sum_{k=0}^\infty \frac{d_k x^k}{k!} \right) \left( \sum_{k=0}^\infty \frac{x^k}{k!} \right)\) via FFT polynomial multiplication in \(O(K \log K)\), then obtain our final answer \(\displaystyle \sum _{i=1} ^N c_i\) in \(O(N)\).