ABC269-F Numbered Checker

問題へのリンク

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("5 4");
            WillReturn.Add("6");
            WillReturn.Add("1 3 2 4");
            WillReturn.Add("1 5 1 1");
            WillReturn.Add("5 5 1 4");
            WillReturn.Add("4 4 2 2");
            WillReturn.Add("5 5 4 4");
            WillReturn.Add("1 5 1 4");
            //28
            //27
            //36
            //14
            //0
            //104
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("1000000000 1000000000");
            WillReturn.Add("3");
            WillReturn.Add("1000000000 1000000000 1000000000 1000000000");
            WillReturn.Add("165997482 306594988 719483261 992306147");
            WillReturn.Add("1 1000000000 1 1000000000");
            //716070898
            //240994972
            //536839100
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("999999999 999999999");
            WillReturn.Add("3");
            WillReturn.Add("999999999 999999999 999999999 999999999");
            WillReturn.Add("216499784 840031647 84657913 415448790");
            WillReturn.Add("1 999999999 1 999999999");
            //712559605
            //648737448
            //540261130
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 998244353;

    static long mHeight;
    static long mWidth;

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        mHeight = wkArr[0];
        mWidth = wkArr[1];

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            long StaY = wkArr[0];
            long EndY = wkArr[1];
            long StaX = wkArr[2];
            long EndX = wkArr[3];

            long Sum1 = DeriveRectSum(EndX, EndY);
            long Sum2 = DeriveRectSum(StaX - 1, EndY);
            long Sum3 = DeriveRectSum(EndX, StaY - 1);
            long Sum4 = DeriveRectSum(StaX - 1, StaY - 1);

            long Answer = Sum1;
            Answer -= Sum2;
            Answer -= Sum3;
            Answer += Sum4;
            Answer %= Hou;
            if (Answer < 0) Answer += Hou;

            sb.Append(Answer);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    // 右下の座標を引数として、矩形(1,1)から(pMaxX,pMaxY)の和を求める
    static long DeriveRectSum(long pMaxX, long pMaxY)
    {
        if (pMaxX < 1 || pMaxY < 1) return 0;

        // 左上の1から右方向への等差数列の項数
        long KouCnt1 = (pMaxX + 1) / 2;
        long SuuretuSum1 = DeriveTousaSuuretuSum(1, 2, KouCnt1, Hou);

        // 奇数行の等差数列の和
        long Syokou2 = SuuretuSum1;
        long KouCnt2 = (pMaxY + 1) / 2;
        long Kousa2 = 2 * KouCnt1 * mWidth;
        long SuuretuSum2 = DeriveTousaSuuretuSum(Syokou2, Kousa2, KouCnt2, Hou);

        // 2行目の、M+2から右方向への等差数列の項数
        long KouCnt3 = pMaxX / 2;
        long SuuretuSum3 = DeriveTousaSuuretuSum(mWidth + 2, 2, KouCnt3, Hou);

        // 偶数行の等差数列の和
        long Syokou4 = SuuretuSum3;
        long KouCnt4 = pMaxY / 2;
        long Kousa4 = 2 * KouCnt3 * mWidth;
        long SuuretuSum4 = DeriveTousaSuuretuSum(Syokou4, Kousa4, KouCnt4, Hou);

        return SuuretuSum2 + SuuretuSum4;
    }

    // 初項と公差と項数と法を引数として、等差数列の和を返す
    static long DeriveTousaSuuretuSum(long pSyokou, long pKousa, long pKouCnt, long pHou)
    {
        pKouCnt %= pHou;
        pKousa %= pHou;
        long Makkou = pSyokou + pKousa * (pKouCnt - 1);
        Makkou %= pHou;
        long wkSum = (pSyokou + Makkou) % pHou;
        wkSum %= pHou;
        long Result = wkSum * pKouCnt;
        Result %= pHou;
        Result *= DeriveGyakugen(2);
        Result %= pHou;
        return Result;
    }

    // 引数の逆元を求める
    static long DeriveGyakugen(long pLong)
    {
        return DeriveBekijyou(pLong, Hou - 2, Hou);
    }

    // 繰り返し2乗法で、(NのP乗) Mod Mを求める
    static long DeriveBekijyou(long pN, long pP, long pM)
    {
        long CurrJyousuu = pN % pM;
        long CurrShisuu = 1;
        long WillReturn = 1;

        while (true) {
            // 対象ビットが立っている場合
            if ((pP & CurrShisuu) > 0) {
                WillReturn = (WillReturn * CurrJyousuu) % pM;
            }

            CurrShisuu *= 2;
            if (CurrShisuu > pP) return WillReturn;
            CurrJyousuu = (CurrJyousuu * CurrJyousuu) % pM;
        }
    }
}

解説

5行7列で考えると下記のグリッドになります。

 1  2  3  4  5  6  7
 8  9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31 32 33 34 35

0に変換できるマスを変換します。

 1  0  3  0  5  0  7
 0  9  0 11  0 13  0
15  0 17  0 19  0 21
 0 23  0 25  0 27  0
29  0 31  0 33  0 35

右下の座標を引数として、(1,1)から右下の座標までの和を返すメソッドを用意できれば、
このメソッドを4回呼ぶことで、矩形の和を求めることができるので、
このメソッドを作ることを考えます。

 1 3 5 7の等差数列の和と
2行下の等差数列の和は、
これまた等差数列になってます。

9 11 13 の等差数列の和と
2行下の等差数列の和は、
これまた等差数列になってます。

よって、等差数列の和の組み合わせで、
(1,1)から右下の座標までの和を求めることができます。