The answer is the sum of all $$$2^n$$$ possible $$$p(x_1,x_2,x_3,....,x_n)$$$ where $$$x_i$$$ is either 1 or -1.It can be computed by counting the number of times k+a comes and the multiplying by its value. This value is divided by $$$2^n$$$.

Let's first solve the problem for $$$n = 1$$$. We can divide the terms of the polynomial in $$$2$$$ categories, terms with even powers and terms with odd powers. We observe that $$$P(1)$$$ is the sum of all coefficients of terms of the polynomial and $$$P(-1)$$$ is the sum of coefficients of terms with even powers subtracted by the sum of coefficients of terms with odd powers. Thus the required sum will be:

Now let's try to generalise this for any $$$n$$$. Say we divide the terms of the polynomial in $$$2^n$$$ categories according to the parities of the powers of the $$$n$$$ variables.

For a particular value of $$$P(x_1,x_2,\ldots,x_n)$$$ where $$$x_i \in {1,-1}$$$, we see that terms of a particular category are either added or subtracted depending on whether the number of variables having odd power in the term and having value $$$= -1$$$ are even or odd respectively.

Consider the sum $$$S$$$ of all $$$2^n$$$ values of $$$P(x_1,x_2,\ldots,x_n)$$$ where $$$x_i \in {1,-1}$$$. Observe that the terms with even powers in all the variables will always be added. Thus, they will appear $$$2^n$$$ times. For terms of any other category, say a category with $$$i > 0$$$ variables having odd powers, the terms will be added if $$$j$$$ of these $$$i$$$ terms have value $$$-1$$$ where $$$j$$$ is a even number. Thus, the terms will be added $$$A$$$ times where,

And the terms will be subtracted $B$ times where,

But we know

This has various proofs.

Thus, these terms will be added and subtracted equal number of times and the final sum $S$ will just be equal to $$$2^n$$$ times the sum of coefficients of all terms with even powers in all the variables. Our required sum will then be $$$\frac{S}{2^n}$$$.

We can find $$$S$$$ in $$$O(n \log{m})$$$ by observing that the value $$$(k + n - 2i)^{m}$$$ appears $$${n}\choose{i}$$$ times.

Code