AOJ本の読書メモ   AOJ    次のAOJの問題へ    前のAOJの問題へ

DPL_5_I: Balls and Boxes 9


問題へのリンク

ボール入れ方に制限なし箱の中身は1つ以下箱の中身は1つ以上
区別できる区別できる123
区別できない区別できる456
区別できる区別できない789
区別できない区別できない101112


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("4 3");
            //6
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 5");
            //42525
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100 30");
            //203169470
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    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 K = wkArr[1];

        // 場合の数[グループ数 , 設置したボールの数] なDP表
        long[,] DPArr = new long[N + 1, K + 1];

        // 最下段を1で埋める
        for (long LoopX = 1; LoopX <= N; LoopX++) {
            DPArr[LoopX, 1] = 1;
        }

        // 斜めのラインを1で埋める
        for (long LoopX = 1; LoopX <= N; LoopX++) {
            for (long LoopY = 1; LoopY <= K; LoopY++) {
                if (LoopX == LoopY) {
                    DPArr[LoopX, LoopY] = 1;
                }
            }
        }

        for (long LoopY = 2; LoopY <= K; LoopY++) {
            for (long LoopX = LoopY + 1; LoopX <= N; LoopX++) {
                // 1つ左のマス値 * グループ数 + 左下のマス値
                long CurrPattern = DPArr[LoopX - 1, LoopY] * LoopY;
                CurrPattern %= Hou;
                CurrPattern += DPArr[LoopX - 1, LoopY - 1];
                CurrPattern %= Hou;
                DPArr[LoopX, LoopY] = CurrPattern;
            }
        }

        //PrintDPArr(DPArr);

        Console.WriteLine(DPArr[N, K]);
    }

    // デバッグ表示
    static void PrintDPArr(long[,] pDPArr)
    {
        for (long Y = pDPArr.GetUpperBound(1); 1 <= Y; Y--) {
            for (long X = 1; X <= pDPArr.GetUpperBound(0); X++) {
                Console.Write("{0,3},", pDPArr[X, Y]);
            }
            Console.WriteLine();
        }
    }
}


解説

DPL_5_I: Balls and Boxes 7で、全部の箱に1以上ある場合の数が解になります。