操作中の駒の座標は整数 \(a,b,c,d\) を用いて \((\frac{a+\sqrt 3 b}{2},\frac{c + \sqrt 3 d}{2})\) と表すことが出来ます。この状態を \(x^ay^bz^cw^d\) と対応させると、求めたい値は \([x^{2H}y^0z^{2W}w^0] \left(x^2+\frac{1}{x^2} + z^2 + \frac{1}{z^2} + (x+\frac{1}{x})(w+\frac{1}{w}) + (y+\frac{1}{y})(z+\frac{1}{z})\right)^N\) となります。

\(X=x+\frac{1}{x}\) とし、他の文字も同じように対応させると上式の括弧内部は \(X(X+W)+Y(Y+Z)-4\) と変形出来ます。よって、\(k=0,1,\dots,N\) について \([x^{2H}w^0] (X(X+W))^k\) を求めることが出来ればよいです。

この式を展開して得られる二項係数の sum の式を畳み込みを用いて高速化するのは難しいです。そこで一度、\([x^{2H}w^0] (X(X+W))^k\) をコマの移動と捉えると、以下のようになります。

始め \((0,0)\) に駒があり、以下の操作を \(k\) 回繰り返したあとに駒が \((2H,0)\) にある操作列の個数

• \(x\) 座標を \(1\) 増やすか減らし、\(x,w\) 座標のどちらかを選び、選んだ座標を \(1\) 増やすか減らす。

始め $(0,0)$ に駒があり、以下の操作を $k$ 回繰り返したあとに駒が $(2H,2H)$ に戻っている操作列の個数

• $x,w$ 座標を両方 $1$ 増やすか減らし、$x,w$ 座標を独立にそれぞれ $1$ 増やすか減らす。

\(x,w\) 座標を両方 \(1\) 増やした回数が \(i\) 回のとき、操作の後半部分では \(x,w\) はそれぞれちょうど \(H+k-i\) 回 \(1\) 増やす必要があるので、この問題の答えは \(\sum_{i=0}^{k} \binom{k}{i} \binom{k}{H+k-i}^2\) となります。

もしくは FPS を用いて処理がしたいならば、\(x=pq,w=\frac{p}{q}\) と置き換えて \([x^{2H}w^0] (X(X+W))^k = [p^{2H}q^{2H}] \left((pq+\frac{1}{pq})(pq+\frac{1}{pq}+\frac{p}{q}+\frac{q}{p})\right)^k= [p^{2H}q^{2H}]\left((pq+\frac{1}{pq})(p+\frac{1}{p})(q+\frac{1}{q})\right)^k\) と変形しても導出できます。

\(k=0,1,\dots,N\) について \(\sum_{i=0}^{k} \binom{k}{i} \binom{k}{H+k-i}^2\) を求めるのは畳み込みで \(\mathrm{O}(N \log N)\) で達成できるため、全体 \(\mathrm{O}(N \log N)\) で解けます。