簡単のため 、\(\displaystyle\sum_{(x_1,x_2,\dots,x_N)\in\bm{X}}\) を\(\displaystyle\sum_{x_1\dots x_N=M}\) と書くことにします。

\(\displaystyle\prod_{i=1}^{N}(x_i+A_i)\) を文字式のまま展開して \(2^N\) 個の項 \(T_1,T_2,\dots ,T_{2^N}\) の和に分解し \(\displaystyle\sum_{s=1}^{2^N}\sum_{x_1\dots x_N=M}T_s\) を計算することを考えると、 \(T_s\) に含まれる \(x_{*}\) の種類に依らず個数のみが重要であることが分かります。つまり、\(x\) の添字を考慮せず \(\displaystyle\prod_{i=1}^{N}(x+A_i)\) を展開し \(B_0+B_1x+\dots +B_Nx^N\) と表したとき,

\[\sum_{k=0}^{N}B_k\sum_{x_1\dots x_N=M}x_1x_2\dots x_k\]

を求めれば良いです。（\(k=0\) のとき \(x_1x_2\dots x_k=1\) です）

ここで \(\displaystyle\sum_{x_1\dots x_N=P}x_1x_2\dots x_k\) は \(P\) に関して乗法的なので、\(M\) を素因数分解して \(M=p_1^{e_1}\dots p_c^{e_c}\) としたとき

\[\displaystyle\sum_{x_1\dots x_N=M}x_1x_2\dots x_k=\prod_{j=1}^{c}\displaystyle\sum_{x_1\dots x_N=p_j^{e_j}}x_1x_2\dots x_k\]

が成り立ちます。\(e_j\) 個の素因数 \(p_j\) を \(x_1,\dots ,x_k\) に \(d(0\le d\le e_j)\) 個、\(x_{k+1},\dots ,x_N\) に \(e_j-d\) 個分配するすべての方法に対する \(p_j^d\) の総和を求めればよく、これは二項係数を用いて簡単な式で表せます。具体的には次のようになります。

\[ \displaystyle\sum_{x_1\dots x_N=p_j^{e_j}}x_1x_2\dots x_k= \begin{cases} \tbinom{e_j+N-1}{N-1}\ &(k=0)\\ \sum_{d=0}^{e_j}p_j^d \tbinom{d+k-1}{k-1}\tbinom{e_j-d+N-k-1}{N-k-1}\ &(0\lt k\lt N)\\ p_j^{e_j}\tbinom{e_j+N-1}{N-1}\ &(k=N) \end{cases} \]

\(B_0,\dots ,B_N\) の計算は畳み込みによって \(\mathrm{O}(N(\log N)^2)\) で、\(M\) の素因数分解は \(\mathrm{O}(\sqrt{M})\) で、その他の計算は \(\mathrm{O}(N\log M)\) の時間計算量で行うことができます。

実装例 (C++)