ARC196 B - Torus Loop
問題概要 問題へのリンク 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 の横の個数は偶数でなければならない.縦も同様....