1番目の公式解説と同じ方針です。ただし、同じ値の選び方は同時に決めます。（これにより多項式のマージテクを行う必要がなくなります）

\({\rm dp_X}[i][j]\) を、「数列 \(X\) から要素を\((i==0?\)偶数:奇数\()\) 個選んで、総和が \(j\) となるような方法の個数」とし、多項式 \({\rm dp'_X}[i]\) を \(\sum_{j}{\rm dp}_X[i][j]x^j\) とします。

\(2\) 個の数列 \(X,Y\) を連結した数列 \(Z\) に対して以下が成り立ちます。

\(\begin{cases} \mathrm{dp'}_Z[0]=\mathrm{dp'}_X[0] \times \mathrm{dp'}_Y[0] + \mathrm{dp'}_X[1] \times \mathrm{dp'}_Y[1] \\ \mathrm{dp'}_Z[1]=\mathrm{dp'}_X[1] \times \mathrm{dp'}_Y[0] + \mathrm{dp'}_X[1] \times \mathrm{dp'}_Y[0] \end{cases}\)

ここで、数列 \(X\) が \(1\) 種類の値のみからなる場合には \(\mathrm{dp}_X\) は容易に計算できることと、数列を並び替えても答えは変わらないことから、もとの数列を同じ値のみからなる数列に分割して上式の通り計算することを考えます。
\(A\) に登場する値の種類数を \(\sigma\) としたとき、高々 \(M\) 次の多項式の乗算を \(O(\sigma)\) 回行うことで元の問題が解けるので、この問題は \(O(N+\sigma M\log M)\) で解くことができました。

実装例(C++)