\(A,B,C,D\) が空でもよいとします．また， \(S=\sum P\) とします．

まず多項式 \(f(x,y)\) を以下のように定めます．

\[f(x,y)=\prod_{p\in P}(x^p+x^{-p}+y^p+y^{-p})=\left(\prod_{p\in P}(x^p+y^p)\right)\left(\prod_{p\in P}(1+(xy)^{-p})\right)\]

このとき答は \(f(x,y)[x^0y^0]\) に等しいです．右辺の括弧内の積をそれぞれ \(g(x,y),h(x,y)\) とします．

\(f(x,y)\) の各項について考えます． \(p\) であって， \(g(x,y)\) で \(x^p\) を選んだものの総和を \(a\) ，\(h(x,y)\) で \((xy)^{-p}\) を選んだものの総和を \(b\) とすると，最終的に \(x^{a-b}y^{S-a-b}\) の項となります．これが定数項になるには， \(a=b=S/2\) が必要十分です．

これは， \(P\) からいくつかの要素を選び総和を \(S/2\) にする方法の数を求め，それを \(2\) 乗すればよいです．部分和問題の要領で \(O(NS)\) で解くことができます．

\(A,B,C,D\) のいずれかが空の場合を考えます． \(A\) が空の場合，制約より \(B\) も空なので， \(C\) の総和を \(S/2\) にすればよく，これも部分和問題です． \(C,D\) が空の場合も同様です．