# ICPC APAC 2024-D Bánh Bò ## 問題文 https://codeforces.com/contest/1938/problem/D $R \times C$ のグリッドを01で埋める方法のうち、任意の $6 \times 7$ の部分行列に含まれる1の個数が全て同じとなる個数 mod 998 ## 解法 条件は以下と同値になる。 - 横に7マス並ぶ列を1段下げても1の個数は同じ（縦も同様） - 各マス $(i,j)$ を $(i\bmod 6,j\bmod 7)$ で見たとき、縦方向が全て同じか横方向が全て同じ これは条件式の差分をとると分かる。2番目の条件から、上から6マスと左から7マス（Ｌ字と呼ぶ）の値を決めるとboardが一意になるので、そのうちvalidな置き方を数えたい。 左上の $6 \times 7$ マスに注目する。各マスで2番目の条件のどちらを（あるいは両方）満たすかを固定したとき、Ｌ字部分の値の決め方が二項係数の積で書ける。（ここまでは定石っぽい）　しかし、状態3通りを各マスで全探索すると $3^{42}$ 通りあり間に合わない。 そこで、「縦方向に埋める（横方向の是非は問わない）」マスの集合を決め打った時の値を代わりに計算することを試みる。これが閉じた式で書ければあとはbitDPのフォーマットで高速に計算できる。実際、集合を決め打った後横方向の是非を決める際に「横方向にのみのびてよいが縦方向はダメ」というマスが生まれるが、これは包除原理で処理できる。 ## 所感 どの配置が許容されているのかをちゃんと整理するのが難しい。