kaage精進録

雑な解説とかライブラリとかおきもちの垂れ流しです。

Codeforces Round #630 (Div.2)-E Height All the Same

面白かったので解説を。

問題概要

グリッドがある。 グリッドの各マスにはいくつかのブロックが積んであり、これに対して次のような操作が行える。

  • 隣り合っている 2 マスを選び、ブロックを 1 つずつ上に積む。
  • 1 マスを選び、ブロックを 2 つ積む。

この操作によって、すべてのマスのブロックの個数を等しくできるような、サイズ n * m で、初期状態でのブロックの個数が l 個以上 r 個以下であるようなグリッドの個数を、\bmod 998244353 で数え上げよ。

考察・解法

3秒くらい考えると、可能か不可能かに影響するのは、それぞれのマスのブロックの個数の偶奇だけであることに気づく。 f:id:kaage:20200409230447p:plain

もう少し実験をするなどして考察をすると、グリッドのマス数が奇数なら、いつでも可能であり、偶数なら、「ブロックの個数が偶数であるようなマスの数」が偶数であれば可能である。

まず、マス数が奇数である場合について、これはいつでも可能なので、通り数は (r-l+1)^{nm}である。

マス数が偶数のときは、l 個以上 r 個以下の奇数の個数を x, 偶数の個数を y として、次のように書ける。

{}_{nm} \mathrm{C}_0 x^0 y^{nm}+{}_{nm} \mathrm{C}_2 x^2 y^{nm-2}+\cdots

めっちゃ二項定理だが、項が1個飛ばしで抜けている。 実はこれは、

\frac{(x+y)^{nm}+(x-y)^{nm}}{2}

と表現することができ、これを\bmod 998244353 で計算することで、この問題が解ける。 計算量は O(\log nm) となる。

感想

結構面白かった。AGCのBの簡単枠にありそう。コンテストの短い時間の中でも安定して解けるくらいにしたい。