Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )
But $g(x,a)$ is linear in $a$ so if you can compute it efficiently for two different values of $a$ then you can compute it efficiently for all $a$?