\(F(x_{1},x_{2},\ldots,x_{N})=\displaystyle\sum_{T \subset \lbrace 1,2,\ldots N \rbrace} \displaystyle\prod_{i \in T} x_{i}\) とおく．

\(\lvert T \rvert = K\) の時の通り数は， \(\left\lbrack\displaystyle\prod_{i=1}^{N} x_{i}^{A_{i}} \right\rbrack(F-1)^{K}\) となる．

よって， \(F^{t}\) の係数は \(\displaystyle\sum_{K=t}^{\mathrm{sum}(A)} (-1)^{K-t} \dbinom{K}{t}\) である．

また， \(F= \displaystyle\prod_{i=1}^{N} (1+x_{i})\) と書けるので， \(\left\lbrack\displaystyle\prod_{i=1}^{N} x_{i}^{A_{i}} \right\rbrack F^{t} = \displaystyle\prod_{i=1}^{N} \binom{t}{A_{i}}\) となる．

これらの両方が \(t=1,2, \ldots\) について列挙できれば良い．

\(t \geq P\) のとき後者が \(\bmod p\) で \(0\) になることをふまえると， \(t \lt P\) として良い．

前者は容易なので割愛して，後者を考えると，これは多点評価の形であるが， \(\bmod p\) での原始根 \(r\) を取ると評価点が等比数列になるのでChirp z-transformで \(\log\) が落とせる．

計算量は \(O(N \log^{2} N + P \log P) ．\)