二次元累積和で条件を書き直してみます．

すると，条件は右下の偶奇を除けば，下端と右端の偶奇が等しい/等しくないという制約が与えられることになるので，適切にその箇所をつないで連結成分ごとに \(2\) 通りの塗り方を掛け合わせればよいです．