次の無向グラフ \(G\) を考えます。

• 各行に対応する \(H\) 個の頂点 \(a_1, a_2, \ldots, a_H\) と、各列に対応する \(W\) 個の頂点 \(b_1, b_2, \ldots, b_W\) の、合計\(H+W\)個の頂点を持つ。
• \(1 \leq i \leq H\) かつ \(1 \leq j \leq W\) を満たす整数の組 \((i, j)\) それぞれについて、頂点 \(a_i\) と頂点 \(b_j\) の間にラベル \(c_{i, j}\) の無向辺がある。
• 上に述べた以外の頂点と辺を持たない。

行に対応する頂点からなる集合を \(\mathcal{R}\) 、列に対応する頂点からなる集合を \(\mathcal{C}\) とおきます。 すなわち、

\(\mathcal{R} := \lbrace a_1, a_2, \ldots, a_H \rbrace\)
\(\mathcal{C} := \lbrace b_1, b_2, \ldots, b_W \rbrace\)

\(G\) は \(\mathcal{R}\) と \(\mathcal{C}\) に分割される二部グラフであることに注意してください。

本問題は、次のように言い換えられます。

\(\mathcal{R}\) に属する頂点からはじめ、「今いる頂点から隣接する頂点に辺を辿って移動する」ことを \(2N\) 回繰り返すとき、辿った辺のラベルを辿った順に繋げて得られるラベルの列 \(d_1d_2\ldots d_{2N}\) としてあり得るものが何通りあるかを求めよ。

動的計画法でこの問題を解きます。

\(\mathrm{dp}[k][v] := \)（現在までにちょうど \(k\) 回の移動を行っており、現在いる頂点が \(v\) であるときの、そこまでに辿ったラベルの列 \(d_1d_2\ldots d_k\) としてあり得るものの個数）

というDPテーブルのおきかたでは、\(1\) つのラベル列を複数回数えてしまい、本問題の正しい答えを得ることはできません。
なぜならば、\(1\) つのラベルの列 \(d_1d_2\ldots d_k\) に対して、そのラベル列を辿った直後の「現在いる頂点 \(v\) 」としてあり得るものは一般に複数あるからです。
これへの対策として、そのラベル列を得たあとの「現在いる頂点 \(v\) 」の代わりに、ラベル列 \(d_1d_2\ldots d_k\) に対して、そのラベル列を辿った直後の「現在いる頂点 \(v\) としてあり得るものすべての集合」を対応させることで、各ラベル列に対応する対象を唯一にすることができ、重複なく数え上げることができます。

つまり、

\(\mathrm{dp}[k][S] := \)（長さ \(k\) のラベル列であって、そのラベル列を辿った直後にいる頂点としてあり得るものすべての集合が \(S\) であるようなものの個数）

とおいて、このDPテーブルを埋めていきます。

グラフ \(G\) は二部グラフなので、

• 偶数回の移動を行った直後にいる頂点は \(\mathcal{R}\) の頂点に限られ、
• 奇数回の移動を行った直後にいる頂点は \(\mathcal{C}\) の頂点に限られます。
  

したがって、

\(\mathrm{dp}[k][S]\) を考える際は、

• \(k\) が偶数のときは、\(S \subseteq \mathcal{R}\) を満たす \(S\) のみを考え、
• \(k\) が奇数のときは、\(S \subseteq \mathcal{C}\) を満たす \(S\) のみを考える

というので十分です。 よって、考えるべきDPの状態数は \(\mathrm{O}(N(2^H + 2^W))\) 個です。

以下で、DPの具体的な方法を述べます。

まず DPの初期状態として、\(k = 0\) の場合の \(\mathrm{dp}[0][\ast]\) を考えます。最初の移動を行う前の位置は \(\mathcal{R}\) に属する頂点から任意に選べるので、

\(\mathrm{dp}[0][\mathcal{R}] = 1\)
\(\mathrm{dp}[0][S] = 0, \,\,\text{for}\,\,S \neq \mathcal{R}\)

です。

次に、DPの遷移を考えます。
長さ \(k\) のラベル列 \(d_1 d_2 \ldots d_k\) を考えます。また、このラベル列を辿った直後にいる頂点としてあり得るものすべての集合を \(S\) とします。
このとき、このラベル列の末尾に数字 \(c\) を付け足した \(d_1 d_2 \ldots d_kc\) について、このラベル列を辿った直後にいる頂点としてあり得るものすべての集合を \(S'_c\) とおくと、

• \(k\)が偶数のとき、\(S'_c = \lbrace b_j : c_{i, j} = c\) となる \(i \in S\) が存在する \( \rbrace \)
  
• \(k\)が奇数のとき、\(S'_c = \lbrace a_i : c_{i, j} = c\) となる \(j \in S\) が存在する \( \rbrace \)

です。
これを踏まえ、末尾に付け足される数字 \(c\) が \(1\) である場合から \(9\) である場合の \(9\) 通りに対応して、

• \(\mathrm{dp}[k+1][S'_1] \leftarrow \mathrm{dp}[k+1][S'_1] + \mathrm{dp}[k][S]\)
• \(\mathrm{dp}[k+1][S'_2] \leftarrow \mathrm{dp}[k+1][S'_2] + \mathrm{dp}[k][S]\)
• \(\mathrm{dp}[k+1][S'_3] \leftarrow \mathrm{dp}[k+1][S'_3] + \mathrm{dp}[k][S]\)
• \(\cdots\)
• \(\mathrm{dp}[k+1][S'_9] \leftarrow \mathrm{dp}[k+1][S'_9] + \mathrm{dp}[k][S]\)

という \(9\) 本の遷移をDPの各状態ごとに行えば良いです。

以上の初期化と遷移によってDPテーブルを埋めれば、本問題の答えが、

\(\displaystyle\sum_{S \in \mathcal{R}} \mathrm{dp}[2N][S] - \mathrm{dp}[2N][\emptyset]\)

として得られます。

以上で本問題を \(O(N(2^H+2^W))\) 時間で解くことができます。