Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$
$$ f(\mathbf{x},n) = \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right) $$ with $\sigma_1,...\sigma_n \in \{1,2,...,N \}$ and $\sigma_i \ne \sigma_j$ for $i\ne j$
(the definition of the $n$-th symmetric sum can also be found here)
Let define $g(\mathbf{x},a)$ be the sum of symmetric sum $$ g(\mathbf{x},a)= \sum_{n=0}^N a^{\mathbb{mod}(n,2)} f(\mathbf{x},n) $$ with $a \in \Bbb R$ and $\mathbb{mod}(n,2) = \begin{cases} 1 \quad \text{ if } n \text{ odd} \\ 0 \quad \text{ if } n \text{ even} \end{cases}$
Example 1: N = 2: $$ g(\mathbf{x},a)= 1 - a(x_1 +x_2) + (x_1 x_2) $$
Example 2: N = 3: $$ g(\mathbf{x},a)= 1 - a(x_1 +x_2+x_3) + (x_1 x_2+x_2 x_3+x_3 x_1) - a x_1 x_2 x_3 $$
The complexity of $g(\mathbf{x},a)$ is $\mathcal{O}(2^n)$ with a naive algorithm. Indeed, the sum $g(\mathbf{x},a)$ has exactly $2^N$ terms and we sum up the terms sequentially
$$ g(\mathbf{x},a)= \sum_{n=1}^N\left( a^{\mathbb{mod}(N,2)} \sum_{\sigma_1,...,\sigma_n} \left(\prod_{i=1}^n x_{\sigma_i}\right)\right) $$
My question: does there exist a better algorithm for computing $g(\mathbf{x},a)$ which is less complex than $\mathcal{O}(2^N)$?
My attempt: There exists special cases where $a=\pm 1$ that can factorize the sum $g(\mathbf{x},a)$ as follows $$ g(\mathbf{x},a)= \prod_{n=1}^N(x_i+a) $$ and then the sum can be computed in $\mathcal{O}(N)$. I try to find a mathematical method like this for $a \ne \pm 1$ without success. In fact, all difficulties lie on the modulo function $\mathbb{mod}(n,2)$.
