ARC143-B Counting Grids

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5");
            //704332752
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100");
            //927703658
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);

        // 全部で何通りあるか
        long AllPatternCnt = DeriveKaijyou(N * N);

        long NGPatternCnt = 0;
        long MaxVal = N * N;

        // 残りの数の階乗を事前計算
        long RestPatternCnt = DeriveKaijyou(N * N - 2 * N + 1);

        // NGマスの数値でループ
        for (long I = N; I <= MaxVal - N + 1; I++) {
            long LowerCnt = I - 1;
            long UpperCnt = MaxVal - I;

            long CurrCnt = DerivePermutation(LowerCnt, N - 1);
            CurrCnt *= DerivePermutation(UpperCnt, N - 1);
            CurrCnt %= Hou;

            CurrCnt *= RestPatternCnt;
            CurrCnt %= Hou;

            NGPatternCnt += CurrCnt;
            NGPatternCnt %= Hou;
        }

        // NGマスの配置場所の分
        NGPatternCnt *= N * N;
        NGPatternCnt %= Hou;

        long Answer = AllPatternCnt - NGPatternCnt;
        if (Answer < 0) Answer += Hou;
        Console.WriteLine(Answer);
    }

    // 階乗 (mod Hou)を求める
    static long DeriveKaijyou(long pN)
    {
        long WillReturn = 1;
        for (long I = 1; I <= pN; I++) {
            WillReturn *= I;
            WillReturn %= Hou;
        }
        return WillReturn;
    }

    // nPr (mod Hou)を求める
    static long DerivePermutation(long pN, long pR)
    {
        long WillReturn = 1;
        for (long I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
            WillReturn %= Hou;
        }
        return WillReturn;
    }
}

解説

どのマスも以下の条件のうち少なくとも一方を満たすようなものの個数個数を 998244353 で割ったあまりを求めてください．
●そのマスに書かれている数より大きい数が書かれているマスが同じ列に存在する．
●そのマスに書かれている数より小さい数が書かれているマスが同じ行に存在する．

とあるので、この条件を満たさないマスについて考えます。
ドモルガンの法則により、OR条件の否定は、AND条件にできるので、下記の条件となります。
●そのマスの値が列Max、かつ、そのマスの値が行Min

5*5のマスで、
条件を満たさないマスが2マス以上存在できるかを考えます。

★→→→→
↑□□□□
↑□□□□
↑□□□□
↑□□□□

すると、
そのマスの値が列Max、かつ、そのマスの値が行Min
という条件から、2マス以上は存在しないことが分かります。

なので、余事象の考え方を使って、
全部の場合の数 - 条件を満たさない場合の数
で解を求めることができます。