I looking for an algorithm to efficiently find the value$\mod p$ of the coefficient of $x^n$ in a generating function of this form:
$$\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$$
where $p$ is some prime of order $2^m$.
What I mean by efficiently: it may be polynomial in $m$, and must be at most logarithmic in $n$ (so basically is must just be polynomial in the input size).
Due to the simple nature of this expression I would imagine that such an algorithm might exist.
The coefficient of $x^n$ is called the Hilbert polynomial. It can be calculated, see the book R. Stanley, Enumerative combinatorics. Vol. 1., Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press. (1999).
See the Theorem 4.1.1 and Proposition 4.1.1 of the book.
Related sofware see here
I sure those calculation can be adapted for the modular case.
Since all reduced to solving of system of linear equations the complexity of the algorithm is polynomial.
Let
$$ \dfrac{1}{\prod\limits_{i=1}^{k}(1-z^{\alpha_i})}=\sum_{n=0}^{\infty}H(n,\alpha)x^n $$
Here is some examples
$$ H(n,1,1,1)=1/2\,{n}^{2}+3/2\,n+1,\\ H(n,1,2,3)=1/12\,{n}^{2}+1/2\,n+1/8\,\cos \left( \pi \,n \right) +2/9\,\cos \left( 2/3\,\pi \,n \right) +{\frac {47}{72}} $$