Число всех невырожденных (т.е. ровно степени $n$) многочленов над полем ${\mathbb{Z}}_p$ равно
$$(p-1)p^n.$$ Обоснование: пусть многочлен записан как $a_n{x}^n+\cdots +a_{1}x+a_0$. Ведущий коэффициент $a_n$ может быть любым ненулевым элементом ${\mathbb{Z}}_p$ — $p-1$ вариантов; остальные $n$ коэффициентов $a_{n-1},\dots ,a_0$ могут принимать любые из $p$ значений каждый, давая в сумме $(p-1)p^n$ вариантов. При этом все коэффициенты берутся по модулю $p$ (т.е. рассматриваются их классы в ${\mathbb{Z}}_p$), поэтому полиномы с коэффициентами, совпадающими по модулю $p$, считаются одним и тем же.
(Если нужно считать полиномы с точностью до умножения на ненулевой скаляр, то количество будет $\frac{p^{n+1}-1}{p-1}$.)