公式解説で言及されている必要条件を経由せずに解を求める方法を記します。

前半部分、つまり、各座標に掛かる係数の多重集合を求めその組み合わせを足し合わせていくというのは同様です。

操作を二分木で表すことを考えます。座標 \(A, B\) に対応する頂点を合体させることで、新たな座標 \(2A - B\) に対応する頂点を作る、というのが問題文の操作です。これを、\(2A - B\) の左の子が \(A\)、右の子が \(B\) として二分木とみなします。

最終的に駒が一つになるまでの操作は一つの根付き二分木としてあらわされます。この二分木に対応する係数の多重集合を考えます。

各葉がはじめの座標に対応しています。 根において値が \(1\) の状態から始め、左に降りる度に \(\times 2\)、右に降りる度に \(\times (-1)\) していったとき最終的な値が葉の係数に対応します。

各中間ノード/葉ノードでの係数はすべて \(\pm 2^k\) の形で表されます。 \(k\) が同じものについて同時に小さいほうから処理していきます。 各 \(\pm 2^k\) に対応するノードから、右側の子を連続で何個生やすかを考えましょう。生やし始めのノードが \((-1)^a 2^k\)、右の子を連続で生やした回数が \(t\) 回のとき、\((-1)^{a+t}\) に対応する葉と、\((-1)^a 2^k\) に対応する頂点が \(\lceil t/2 \rceil\) 個、\((-1)^{a+1} 2^k\) に対応する頂点が \(\lfloor t/2 \rfloor\) 個新しく生まれます。

よって、\(-2^k, +2^k\) がそれぞれ何個あるかを管理すれば十分なことがわかります。(\(k\) の値は持つ必要がありません。)

dp テーブルを以下のように定義します。 今見ているのが \(\pm 2^k\) の頂点として、 \(dp[x][y][z] = \left( \text{葉を} x \text{個決めていて} (2^k) \text{が} y \text{個} \left(-2^k\right) \text{が} z \text{個の場合の数} \right)\)

遷移として、\(\pm 2^k\) の頂点を追加でいくつか生やすか、その際偶奇の割り振りをどのようにするか、を決めれば十分です。ただし、重複は数えないように注意することが必要です。

遷移としてありうるものを列挙し、重複を取り除いたとしても計算量はテーブルに \(3\) 乗、遷移に (いくつ増やすか) (奇数を何個割り当てるか)^2 の\(3\) 乗を合わせ、全体で \(O(N^6)\) となります。定数倍も非常に小さく、十分に高速です。