we should have $p(z) = \sum_{i=1}^{k} a_i x_i 4^{i-1}=\sum_{i=1}^{k} x_i 4^{i-1}=z$ so $4$ divide $x_i(a_i-1)$ or $x_i(a_i-1)+1$ depanding of $a_{i-1}$ and $x_{i-1}$ values if $4$ divide $x_i(a_i-1)$ if $a_i=0$, $x_i\in 0,1,2,3$ so $4$ cases if $a_i=1$, $x_i\in 0,1,2,3$ so $4$ cases if $a_i=2$, $x_i\in 0$ so $1$ case if $a_i=3$, $x_i=0,2$ but if $x_i=2$, $x_{i+1}$ can only be $1$ or $3$ depending of $a_{i+1}$ because 4 divide $x_{i+1}(a_{i+1}-1)+1$ the case where $x_i=0$ doesn't affect $x_{i+1}$ choice. anyway we have $4$ possibilities $(x_i,x_{i+1})=(0,0),(0,1),(0,2),(0,3)$ or $1$ possibility $(x_{i},x_{i+1})=(2,1)$ if $a_{i+1}=0$ or $(x_{i},x_{i+1})=(2,3)$ if $a_{i+1}=2$ so the number of elements of $A$ is a multiplication of $1's$ or $4's=$ power of $2$$