包除原理で問題を解くことを考えます。

「長さ \(N\) の正整数列で、総積が問題中で与えられた値であり、数列の先頭 \(i\) 項が平方数であるようなものの個数」を \(f(i)\) とします。このとき、求める答えは \(\displaystyle \sum_{i=0}^{N}(-1)^i\binom{N}{i} f(i)\) です。\(f(i)\) を求めることを考えます。

整数が平方数であることは、素因数分解したときの指数が全て偶数であることと同値です。したがって、「長さ \(N\) の非負整数列で、総和が \(e\) であり、数列の先頭 \(i\) 項が偶数であるようなものの個数」を \(g(i,e)\) とすると、\(\displaystyle f(i)=\prod_{k=1}^{K} g(i,E_i)\) となります。

\(g(i,e)\) について考えます。明らかに

\[g(N,e)=\begin{cases} 0 && \text{(e is odd)}\\ \binom{\frac{e}{2}+N-1}{N-1} && \text{(e is even)} \end{cases}\]

が成り立ちます。また、数列の第 \(i+1\) 項の偶奇で場合分けすることで、\(g(i,e)=g(i+1,e)+g(i+1,e-1)\) が成り立つことがわかります。よって、\(g(i+1,*)\) から \(g(i,*)\) を \(O(\max E_i)\) で必要なところまで求めることができます。

以上より、\(i\) の降順に計算することで、各 \(f(i)\) を \(O(K+\max E_i)\) で求めることができるので、全体で \(O(N(K+\max E_i))\) で元の問題に答えることができます。

実装例(C++)