AOJ 0537 ビンゴ

問題へのリンク

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("3 9 45");
            WillReturn.Add("3 100 50");
            WillReturn.Add("5 50 685");
            WillReturn.Add("0 0 0");
            //1
            //7
            //74501
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const long Hou = 100000;

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

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

        foreach (string EachStr in InputList) {
            SplitAct(EachStr);
            long N = wkArr[0];
            long M = wkArr[1];
            long S = wkArr[2];
            if (N == 0 && M == 0 && S == 0) break;

            long Result = Solve(N, M, S);
            Console.WriteLine(Result);
        }
    }

    static long Solve(long pN, long pM, long pS)
    {
        // 場合の数[和,使用した数]なインラインDP表
        long UB0 = pS;
        long UB1 = pN * pN;

        long[,] DPArr = new long[UB0 + 1, UB1 + 1];
        DPArr[0, 0] = 1;

        for (long I = 1; I <= pM; I++) {
            for (long J = UB0; 0 <= J; J--) {
                long NewJ = J + I;
                if (NewJ > UB0) continue;

                for (long K = UB1; 0 <= K; K--) {
                    if (DPArr[J, K] == 0) continue;
                    long NewK = K + 1;
                    if (NewK > UB1) continue;

                    DPArr[NewJ, NewK] += DPArr[J, K];
                    DPArr[NewJ, NewK] %= Hou;
                }
            }
        }

        return DPArr[UB0, UB1];
    }
}

解説

考察すると
狭義単調増加なす数列で
項数が和が指定されていると考えることができるので

場合の数[和,使用した数]なインラインDP表を更新してます。