DPL_5_G: Balls and Boxes 7

問題へのリンク


  
ボール
箱
入れ方に制限なし
箱の中身は1つ以下
箱の中身は1つ以上
  
区別できる
区別できる
1
2
3
  
区別できない
区別できる
4
5
6
  
区別できる
区別できない
7
8
9
  
区別できない
区別できない
10
11
12

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 5");
            //5
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 3");
            //41
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("100 100");
            //193120002
        }
        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);

        long Answer = 0;
        for (long LoopY = 1; LoopY <= K; LoopY++) {
            Answer += DPArr[N, LoopY];
            Answer %= Hou;
        }
        Console.WriteLine(Answer);
    }

    // デバッグ表示
    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();
        }
    }
}

解説

縦軸をグループ数、横軸を設置したボールの数 として、
ボールが5個、箱が3個
でDPを考えます。

最下段は1で埋まり、
左下の1の、右上のラインも1で埋まります。

３｜□□１□□
２｜□１□□□
１｜１１１１１
ーーーーーーー
　｜１２３４５

他のマスは、左下のマスからは、そのまま遷移できて、
1つ左のマスからは、グループ数のどれかのグループに追加する場合の数なので

左下のマスの場合の数 + 1つ左のマスの場合の数 * グループ数(縦軸の目盛)
で分かります。

３｜□□１６25
２｜□１３７15
１｜１１１１１
ーーーーーーー
　｜１２３４５