ABC127-E Cell Distance

問題へのリンク

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 2 2");
            //8
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 5 4");
            //87210
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100 100 5000");
            //817260251
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mK;

    const long Hou = 1000000007;

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long N = wkArr[0];
        long M = wkArr[1];
        mK = wkArr[2];

        long Result1 = DerivePatternCnt(M, N);
        long Result2 = DerivePatternCnt(N, M);
        long Answer = Result1 + Result2;
        Answer %= Hou;
        Console.WriteLine(Answer);
    }

    // 全ての配置で、X成分のみのマンハッタン距離の総合計を返す
    static long DerivePatternCnt(long pYokoHaba, long pTateHaba)
    {
        long DistanceSum = 0;

        // 2つのみ配置する場合の、X成分のみのマンハッタン距離でループ
        for (int I = 1; I <= pYokoHaba - 1; I++) {
            long PatternCnt = pYokoHaba - I;

            PatternCnt *= pTateHaba;
            PatternCnt %= Hou;
            PatternCnt *= pTateHaba;
            PatternCnt %= Hou;

            DistanceSum += I * PatternCnt;
            DistanceSum %= Hou;
        }

        // 2つ配置して、残りの配置の場合の数
        long R = pYokoHaba * pTateHaba - 2;
        long ChooseCnt = DeriveChoose(R, mK - 2);

        DistanceSum *= ChooseCnt;
        DistanceSum %= Hou;
        return DistanceSum;
    }

    // nCr (mod Hou)を求める
    static long DeriveChoose(long pN, long pR)
    {
        if (pN < pR) return 0;

        pR = Math.Min(pR, pN - pR);

        long WillReturn = 1;
        for (long I = pN - pR + 1; I <= pN; I++) {
            WillReturn *= I;
            WillReturn %= Hou;
        }
        for (long I = 2; I <= pR; I++) {
            WillReturn *= DeriveGyakugen(I);
            WillReturn %= Hou;
        }
        return WillReturn;
    }

    // 引数の逆元を求める
    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;
        }
    }
}

解説

マンハッタン距離は、X成分とY成分がありますがX成分のみで考えます。
(Y成分について盤面を90度回転させて、足し算すればいいです)

5*5の盤面に5つ配置するとして、
縦幅を無視して、まずは2個配置するとして、
X成分の距離ごとの配置が何通りあるかを考えます。

距離が1の配置は、下記の4通り
駒駒□□□
□駒駒□□
□□駒駒□
□□□駒駒

距離が2の配置は、下記の3通り
駒□駒□□
□駒□駒□
□□駒□駒

距離が3の配置は、下記の2通り
駒□□駒□
□駒□□駒

距離が4の配置は、下記の1通り
駒□□□駒

簡単な数列になってるのが分かります。
縦幅5を無視したので、これを考慮すると
各場合に対して、重複順列の場合の数である5*5を掛けた、場合の数になります。

全ての配置のマンハッタン距離の総和が欲しいので
全ての配置での、距離が1の配置の場合の数*1
全ての配置での、距離が2の配置の場合の数*2
全ての配置での、距離が3の配置の場合の数*3
全ての配置での、距離が4の配置の場合の数*4
を総合計すれば、漏れなく重複なく計上できるので
これが解になります。

なので、残りの配置のChooseを求めて、掛けてます。