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

問題概要

$n * m$ の盤面が与えられます。 $a_{i,j}$ 個の箱が座標 $(i, j)$ に積み上げられている盤面を初期盤面と呼びます。以下の処理を繰り返し、すべての盤面の高さを揃えるゲームをします。

2つの隣り合う箱の上に一つずつ箱を積み上げる
一つの箱の上に二つの箱を積み上げる

揃えることができたらゲームクリアです。 $L \le a_{i,j} \le R$ であるすべての初期盤面の中で、クリアできる盤面の個数を求めてください。 f:id:coonevo:20200402043759p:plain

解説

処理をまとめる、減らす、単純化する

今回の処理の性質において大切なのは、「高さをすべて等しくすることは、偶奇を揃えることである」ということです。なぜなら、偶奇を揃えることができたら、その後処理2.を使えば高さも揃えることができるからです。よって問題は、「処理1.で偶奇を揃えることができるか？」というものに変わります。

これで処理が減りました。嬉しいです。

また、使える数の個数を $R-L + 1 :=K$ とおき、 $1 \le a_{i,j} \le K$ に変えます。こうしても問題に影響がないです。なぜなら、今回の問題は偶奇性に着目するだけになったからです。

※使える数を簡単のために1 ~ Kにしておこう程度のものです。最後の考察でわかりやすくするためなので、今はあまり気にしないでください。

任意の盤面のペアのみの偶奇を変えることができる

ここで、処理1.をうまく使うと、他の盤面の偶奇を変えることなく、ある盤面のペアの偶奇のみを変えることができることを示します。考察を発展させるための重要ポイントです。あるペア間のpathを $w_1 \rightarrow w_2 \rightarrow ... \rightarrow w_N$ とすると、そのpathを走査するように処理1.をすることで実現できます。

画像にするとわかりやすいです。最初と最後のみが1回、間が2回箱が乗るので、最初と最後のみ偶奇が反転します。

f:id:coonevo:20200402010321j:plain

これにより、偶数個の偶奇が同じものは、すべて逆の偶奇に変換できることがわかりました。

盤面の数の偶奇

n * m が奇数の場合

結論からいうと、どんな盤面でも成功させることができます。なぜなら、偶奇のどちらかが偶数個になるからです。偶数個になった方を、すべて逆の偶奇に変換できることが先ほど示されているので、この初期盤面からは、必ず偶奇を揃えることができます。

よって答えは、すべての盤面がすべての数を取りうるので $K^{n m}$ になります。以降、これを $total$ とします。

n * m が偶数の場合

条件1. $\sum_i \sum_j a_{i,j}$ が偶数の場合

偶奇ともに偶数個なので、すべて条件を満たします。

条件2. $\sum_i \sum_j a_{i,j}$ が奇数の場合

偶奇ともに奇数個です。ここから成功することはできません。

よって以上の2つの条件を満たす初期盤面が、totalのうちいくつずつあるのかを知りたいです。結論からいうと、だいたい半分ずつです。だいたいというのは、 $total$ は偶数とは限らないからです。totalの偶奇は、使える数の個数 $K$ の偶奇に依ります。

ここで更なる条件分岐をします

使える数の個数 $K$ が偶数のとき

条件1,2を満たす場合の数はともに $\frac{total}{2}$ です。これは、たとえば以下のように示すことができます。

例えば、

$a_{1,1} = 1$ である盤面 $x$ と、
他の盤面が $x$ と全く同じで $a_{1,1} = 2$ であるような盤面 $y$

をペアにします。すると、これらのペアは条件1をともに満たすことはありません。つまり、一方が条件1を満たせば、他方は条件2を満たします。和の偶奇が変わっていますからね。

このペアリングを、取りうるすべての奇数 $a_{1,1} = 2z-1 (1 \le z \le \frac{K}{2})$ について行いましょう。

つまり、

$a_{1,1} = 2z-1$ である盤面 $x_z$ と、
他の盤面が $x_z$ と全く同じで $a_{1,1} = 2z$ であるような盤面 $y_z$

をペアにします。

すべての場合の数を網羅しながら、条件1と2はちょうど半分に分かれることがわかります。

$K$ が奇数のとき

こちらは、少し複雑ですが、同様のペアリングを考えましょう。 $K$ は奇数ですが、先ほどのペアリングアルゴリズムは $a_{1,1} = 2z-1 (1 \le z \le \frac{K-1}{2})$ まで適用することができます。

$a_{1,1} = K$ の場合のみ別で処理します。

なぜなら、ペアリングの相手である $a_{1,1} = K +1$ を使うことができないからです。

盤面内に $a_{i,j} \lt K$ を満たす $i, j$ が存在するのであれば、先ほど同様にそこを起点としてペアリングを行えばよいです。

そのような $i, j$ が存在しない、つまり、すべての要素が $K$ であるような盤面は、誰ともペアを作れませんでした。この盤面は、条件1と2どちらを満たすのでしょうか？答えは、もちろん条件1です。

つまり、この条件1に割り振られた仲間外れ盤面（オール $K$ 盤面）以外はすべてペアを作り、それぞれ条件1と2に分かれました。条件1の個数はいくつですか？

$\frac{total - 1}{2} +1$ ですね。

以上で解説を終わります。

実装

提出へのリンク

#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;

struct mint {
    /* 省略 */
};
int main() {

    ll n, m, l, r;
    cin >> n >> m >> l >> r;
    mint ans;
    mint total_grid_num = mint(r - l + 1).modpow(n * m);
    if(n * m % 2 == 1){
        ans = total_grid_num;
    }
    else{
        if((r - l + 1) % 2 == 0){
            ans = total_grid_num * mint(2).inv();
        }
        else{
            ans = (total_grid_num - 1) * mint(2).inv() + 1;
        }
    }
    cout << ans << endl;
}