問題概要
1辺の長さが1の正方形である2種類のタイルがある．
- 種類A:
- 種類B:
高さ $H$，幅 $W$ のグリッドに，このタイルが敷き詰められている．
(A, B からなる長さ $W$ の文字列が $H$ 個与えられる)
各タイルは回転可能． グリッドをトーラスとしてみたときに，線分が行き止まりにならずつながるように配置する方法の数を mod 998244353 で求めよ．
制約
$2 \leq H$，$2 \leq W$，$HW \leq 10^6$
解
略解．click to open
正しく敷き詰められているとする． $p[i, j]$ を，セル $(i, j)$ の左側の縦の線分の中点を線が通るかどうか (true/false) $q[i, j]$ を，セル $(i, j)$ の上側の横の線分の中点を線が通るかどうか (true/false) とする． トーラスになるように同一視する．
$i$を固定し，横一列に $p[i, j]$ ($j = 0, 1, \ldots, W)$ を考えると，
- セル $(i, j)$ が
Aなら，$p[i, j] = \neg p[i, j + 1]$ - セル $(i, j)$ が
Bなら，$p[i, j] = p[i, j + 1]$
だから，A の横の個数は偶数でなければならない．縦も同様．
次に，$(i, j)$ に B が置かれているとする．
- $(i, 0)$ から $(i, j - 1)$ までの
Aの数の偶奇によって，$p[i, 0] \texttt{ XOR } p[i, j)$ の true/false が決まる． - $(0, j)$ から $(i - 1, j)$ までの
Aの数の偶奇によって，$q[0, j] \texttt{ XOR } q[i, j)$ の true/false が決まる． - 当然，$p[i, j] \texttt{ XOR } q[i, j] = \texttt{false}$ である．
であるから，
- $(i, j)$ に
Bが置かれていると，$p[i, 0] \texttt{ XOR } p[0, j]$ の true/false は決まっている． これを $r(i, j)$ とする．
そこで，$\{(i, 0) \mid i = 0, \dots, H - 1\} \cup \{(0, j) \mid j = 0, \dots, W - 1\}$ を頂点とする二部グラフを，
B が置かれている $(i, j)$ に対して $(i, 0)$ と $(0, j)$ を，重み $r(i, j)$ で結ぶように作る．
全頂点に矛盾無くポテンシャルが定義できなければならない．
逆に，全頂点にポテンシャルが定義できれば，それにしたがって すべての $p[i, j], q[i, j]$ が定義できる．
したがって，求める答は，上の二部グラフの連結成分数を $S$ として，$2^S$ である．