Let \(P(\cdot)\) and \(E[\cdot]\) denote the probability and expected value, respectively. For \(i=0,1,\dots,N\), we have \(P(x'=2i-N)=\frac{1}{2^N}\binom{N}{i}\), and the answer is \(E[|x'-X|]\).

Since \(P(|x'|\leq N)=1\), and \(E[x']=0\) by symmetry of the moves, for \(X \geq N\) we have:

\[E[|x'-X|]=E[X-x']=E[X]-E[x']=X.\]

Likewise, for \(X \leq -N\), \(E[|x'-X|]=-X\).

Let \(-N \lt X \lt N\), denote by \(\mathbf{1}\) the indicator function, and let \(M=\lceil\frac{N+X}{2}\rceil\). Then

\[\begin{aligned} E[|X-x'|] &=E[x'-X]+2E\left[(X-x')\mathbf{1}_{\{x' \lt X\}}\right]\\ &=-X+2E\left[(X-x')\mathbf{1}_{\{x' \lt X\}}\right]\\ &=-X+2\sum_{i=0}^{M-1}(N+X-2i)P(x'=2i-N)\\ &=-X+\frac{1}{2^{N-1}}\sum_{i=0}^{M-1}(N+X-2i)\binom{N}{i}. \end{aligned}\]

So it suffices to compute the following values:

\[ f(N,M)=\sum_{i=0}^{M-1}\binom{N}{i},\quad g(N,M)=\sum_{i=0}^{M-1}i\binom{N}{i} \]

The function \(f\) satisfies \(f(N,M+1)-f(N,M)=\binom{N}{M}\) and

\[\begin{aligned} f(N+1,M) =\sum_{i=0}^{M-1}\binom{N+1}{i} =\sum_{i=0}^{M-1}\left(\binom{N}{i-1}+\binom{N}{i}\right) =2f(N,M)-\binom{N}{M-1}. \end{aligned}\]

By precalculating the factorials to enable \(O(1)\) computation of a binomial coefficients, one can apply Mo’s algorithm to compute \(f(N,M)\) for all \((N,M)\) of interest (across all test cases) in a total of \(O(\max (N+|X|)\cdot\sqrt{T})\) time. The function \(g\) can be evaluated likewise, using the properties \(g(N,M+1)-g(N,M)=M\binom{N}{M}\) and \(g(N+1,M)=2g(N,M)+f(N,M)-M\binom{N}{M-1}\).

Sample code (C++) / Sample code (Python)