2 変数母関数(bivariate generating function, BGF)を考えましょう。1 回の移動を母関数で表すと

\[\left(\sum_{i=0}^1 x^i \right)\left(\sum_{i=0}^\infty y^i \right) - x^0 y^0 = \frac{1+x}{1-y} - 1 = \frac{x+y}{1-y}\]

となります。よって求めたいものは

\[ \begin{aligned} & [x^N y^M] \sum_{i=0}^\infty \left( \frac{x+y}{1-y} \right)^i \\ &= [x^N y^M] \frac{1}{1-\frac{x+y}{1-y}} \\ &= [x^N y^M] \frac{1-y}{1-x-2y} \\ &= [x^N y^M] \frac{1}{1-x-2y} - [x^N y^M] \frac{y}{1-x-2y} \\ &= [x^N y^M] \frac{1}{1-x-2y} - [x^N y^{M-1}] \frac{1}{1-x-2y} \\ \end{aligned} \]

です。ここで第 1 項について、

\[\frac{1}{1-x-2y} = \sum_{i=0}^\infty (x+2y)^i\]

で、右辺で \(x^N y^M\) が登場するのは \(i=N+M\) のときだけなので

\[[x^N y^M] \frac{1}{1-x-2y} = [x^N y^M] (x+2y)^{N+M} = \binom{N+M}{N}2^M\]

です。第 2 項も同様に計算すると、答えは

\[\binom{N+M}{N}2^M - \binom{N+M-1}{N}2^{M-1}\]

であるとわかり、これは \(\mathrm{O}(N+M)\) で計算できます。