# ARC193 C Grid Coloring

[リンク](https://atcoder.jp/contests/arc193/tasks/arc193_c)

### 方針

十字の操作ではなく行or列を選んで1色に塗る、という操作で作れるグリッドの個数を考えてみます。
$dp_{h, w}$ = $h$行$w$列のグリッドの塗り分け方の個数
とします。
操作を逆から見ていきます。操作を行える箇所について包除をすることを考えると以下のような遷移が立ちます。

$$dp_{h, w} = \sum_{1 \leq i \leq h} (-1)^{i-1} C^i \binom{h}{i} dp_{h - i, w} + \sum_{1 \leq j \leq w} (-1)^{j-1} C^j \binom{w}{j} dp_{h, w -j} + \sum_{1 \leq i \leq h, 1 \leq j \leq w} (-1)^{i + j - 1} C \binom{h}{i} \binom{w}{j} dp_{h - i, w - j}$$

この式をそのまま計算すると4乗になって厳しいですが 3番目の項は $\sum_{1 \leq i \leq h} (-1)^i \binom{h}{i} dp_{h - i, j}$ を各 $(h, j)$ で前計算しておけば 3乗で計算できます。

元の問題に戻ります。
最後の手の十字の操作が行えればあとは上で計算したものから答えを求めることができます。
これも操作可能な場所についての包除を行うことで計算できます。

[実装例](https://atcoder.jp/contests/arc193/submissions/63118657)

#### 追記中(2025/03/31)
初手の包除の立式について詳細を書く