AtCoder Regular Contest 157 D問題メモ

AtCoder Regular Contest 157

久々にひっどい誤読（思い込み）をB問題でやっちゃった。

D - YY Garden

• $H \times W$ のグリッドに 'X' または 'Y' が1つずつ書かれている
• 行と行の間、または列と列の間に一直線に区切りを入れることを繰り返して、複数の区画に区切る
  • 区切りはグリッドの途中で止まったりせず、端から端まで貫通する
• 区切る場所は行方向に $H-1$、列方向に $W-1$ 箇所あるため、区切り方は $2^{H+W-2}$ 通りある
• このうち、「どの区画にも、ちょうど2個の'Y'が含まれるような区切り方」の個数を $\mod{998244353}$ で求めよ
• $1 \le H,W \le 2000$

区切りは板チョコのように、行・列とも一直線に端から端まで入る。（明治のTHE・チョコレートは例外）

区切るべき区画の個数は、初期盤面にある 'Y' の個数で一意に決まる。
'Y' が奇数個なら不可能。偶数個なら、$2n$ とすると、$n$ 個の区画に分けることになる。

行方向に区切る数、列方向に区切る数をそれぞれ $R,C$ とすると、$n=RC$ なので、 $(R,C)$ の組は $n$ を2整数の積に分ける方法の数に限定される。
さらに $H \ge R,W \ge C$ という制約もある。

この $(R,C)$ を全探索する。

$R,C$ を固定した時にどうなっていればいいかというと、'Y' の個数の2次元累積和を取ったときに

    :     :     :         :
... 2 ... 4 ... 6 ... ...2C
    :     :     :         :
... 4 ... 8 .. 12 ... .. 4C
    :     :     :         :
    :     :     :         :
...2R .. 4R .. 6R ... ..2RC

このような条件を満たす $n$ 個のマスが存在していればよいことになる。
これらの各マスのすぐ右・すぐ下に区切りを入れることで、全ての区画の'Y'を2個ずつにできる。

途中の行・列はどこでもよいのだが、最終行・最終列は必ず使わなければならない点に注意。

ここで面倒なのが、上の条件を満たすマスの配置は複数出てきてしまうことがあり、 それらは別の区切り方として数えなければならない点。

累積和の $i$ 行目の $j_1,j_2,...$ 列目を拾うと $2k,4k,...,2Ck$ の並びが現れるとする。
また、$i+1$ 行目でも同じ列を拾うと、同じ$2k,4k,...,2Ck$ の並びが現れるとする。
この時、グリッドの $i+1$ 行目は全て 'X' となっているはずである。
$i$ 行目の直後に区切りを入れるのと、$i+1$ 行目の直後に入れるのとの違いで、全体の可能不可能に影響はもたらさない。

よって、最初に全て 'X' である行・列を除いてやれば、$(R,C)$ を固定した時の $n$ 個のマスは必ず一意に定まる。
少なくとも最終行・最終列が続けて同じ数ということが無くなるので、 最終行で $2R,4R,...,2RC$、最終列で $2C,4C,...,2RC$ の並びが現れる位置をそれぞれ調べ、 現れるなら、他の箇所も満たされるか調べればよい。

除いた盤面で、ある行の直後に区切りを入れることになった場合、元の盤面に戻って区切りを実際に入れる箇所の候補は、 「自身、および自身から次に除かない行が出てくるまでに除いた行」の直後となる。

     ... 2k ... 4k ..... 2Ck    __ ←除いた盤面でのこの行における
(除) ... 2k ... 4k ..... 2Ck    __   元の盤面での区切り位置候補は3箇所
(除) ... 2k ... 4k ..... 2Ck    __
     ... 2k ..4k+1 ... 2Ck+5

この候補は、区切りを入れる位置に対してそれぞれ独立に存在する。

よって一意に定まった区切り位置に対して、各位置の候補数の積が、$(R,C)$ を決め打ったときの答えとなる。
（※最終行・最終列に関しては候補数は1固定である点に注意）

前処理に $O(HW)$、その後1回の $(R,C)$ の決め打ちで $n$ 個（最大 $HW/2$）のマスを参照することになるが、

• $n$ が最大に近いなら、$H \ge R,W \ge C$ という制約のため、$(R,C)$ の候補は多くない
• $n$ が小～中程度なら、$(R,C)$ の候補は多少増えうるが、1回の探索にかかる負担は少ない

ため、正確な計算量解析は難しいが、2秒あれば十分通る計算量となる。

Python3