以下、長方形の \(2\) 行それぞれを上段下段と呼びます。

敷き詰めるのに使う多角形の性質を考えます。

使う多角形は上段の連続するいくつかのマスと下段の連続するいくつかのマスからなるもののみを考えればよいです。これは、そうでない多角形を使用すると長方形の全てのマスを敷き詰めることができないことからわかります。

敷き詰める順番を決めると、見通しが立てやすくなります。長方形の左側から敷き詰めていくことにしましょう。つまり、あるマスが既に敷き詰められているとき、同じ段のそのマスより左側のマスに敷き詰められていないものが存在しないような順番で敷き詰めます。

DP を行います。\(\mathrm{dp}[i][j]\) を

\(\mathrm{dp}[i][j]\) := \(i\) 個の多角形を既に使用していて、上段の方が敷き詰められているマスが \(j\) 個多いような敷き詰め方の通り数

と定義します。\(i,j\) から上段と下段の敷き詰められているマスの数を求めることが可能です。

まず、\(j\) のとりうる値の範囲を考えます。

\(j > M\) と \(j < -M\) の場合を考える必要はありません。また、\(j = M\) と \(j = -M\) の場合は、重複を考えるとどちらか一方のみを考えればよいです。よって、\(2M\) 通りの値のみを考えればよいです。

次に、遷移を考えます。

\(\mathrm{dp}[i][j]\) の状態から \(\mathrm{dp}[i+1][k]\) の状態に遷移する時、追加する多角形は一意に定まります。そのため、追加する多角形が連結でかつ \(k\) が上で述べた範囲に収まるような全ての \(\mathrm{dp}[i+1][k]\) に \(\mathrm{dp}[i][j]\) を加算すればよいです。

以上の DP は、\(Θ(NM^2)\) の計算量で動作します。これは一部テストケースにおいて間に合いません。この DP を高速化することを考えます。

実は、\(\mathrm{dp}[i][j]\) の \(j\) の偶奇が \(iM\) の偶奇と等しくないものを考える必要はありません。そして、\(j\) として偶数のみもしくは奇数のみを考えると、この DP の遷移は区間への加算とみなすことができます。いもす法と呼ばれるテクニックを用いることで、計算量を \(Θ(NM)\) に削減できます。これは十分高速に動作します。提出コード (C++)