ARC143 B - Counting Grids 解説

問題

のマス目の各マスに 1 から までの整数を 1 つずつ書き込む方法であって， どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数を 998244353 で割ったあまりを求めてください．

• そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する．
• そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する．

解法

まず問題から、数学で解くか、剰余を取れと言われているのでDPで解くと検討をつける。まずは数学で考察してみよう。
シンプルに考えると数え上げの雰囲気だが、そのまま数え上げようとしても剰余を取らせる以上愚直は無理、かといって効率のいい数え上げ方法も見つかりづらい。
ここで、条件を見てみると、「AまたはB」の形になっている。このタイプの数え上げは余事象(AでなくBでもない)を考えるといいと相場がきまっている。考察してみよう。

すると、「条件を満たさない盤面の中で、条件を満たさないマスは高々1つ」と仮定すると、余事象の数え上げは、そのマスに書かれた数から以下のようにして簡単にできそう

• 同じ列: より小さい数個から個選んで並べる
• 同じ行: より大きい数個から個選んで並べる

この部分がで、を全探索するとき、全体で計算量はで十分高速。あとは、それぞれに(または探索後の合計値に)残った個のマスに余った数を適当に並べる場合の数をかけてあげれば余事象の数え上げは完了。

ただ、これで終わりではない(いいけど)。仮定の証明が必要だ。今回、

「条件を満たさない盤面の中で、条件を満たさないマスは高々1つ」

という仮定があるので、これを考察してみる。 まず、条件を満たさないマスともう一つのマスについて、としてみる。
このとき、Yと同じ列で、Xと同じ行にあるマスは　Xより大きいので当然Yよりも大きい。となるととなるYは全て条件を満たす。
同様に、についても同じように考えると、これも条件を満たす。
以上から、条件を満たさないマスは高々1つということがわかったので、ここまでの解法が合っていることがわかった。

実装

int main(){
    ll n;
    cin >> n;

    modint<998244353>ans = 1; // 答え
    modint<998244353>no = 0; // 余事象
    modint<998244353>offset = 1; // 残りのマスの並び替え
    rep(i, n*n-2*n+1)
    {
        offset *= i + 1;
    }

    rep (i, n*n)
    {
        ans *= i + 1;
        modint<998244353>cnt = 1;
        rep(j, n-1)
        {
            cnt *= i-j; // Xより小さい数の順列

            cnt *= (n*n-i-1)-j; // Xより大きい数の順列
        }

        no += cnt * n * n * offset; // 数え上げ*場所*残り
    }

    cout << (ans - no).value() << endl;
}