https://kaage.hatenablog.com/entry/2020/04/09/232214

面白かったので解説を。

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

この操作によって、すべてのマスのブロックの個数を等しくできるような、サイズ $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の簡単枠にありそう。コンテストの短い時間の中でも安定して解けるくらいにしたい。