Problem181 2色の物体をグループ分けする場合の数

問題

3つの黒い物 B と1つの白い物 W を持っているとき,
これらは7通りにグループ分け出来る.
(BBBW)
(B,BBW)
(B,B,BW)
(B,B,B,W)
(B,BB,W)
(BBB,W)
(BB,BW)

60個の黒い物 B と40個の白い物 W は何通りにグループ分け出来るか?

ソース

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Solve(3, 1);
        Solve(60, 40);
    }

    struct PairInfoDef
    {
        internal int BCnt;
        internal int WCnt;
    }

    static void Solve(int pBCnt, int pWCnt)
    {
        //場合の数[Bの個数,Wの個数]なDP表
        long[,] DPArr = new long[pBCnt + 1, pWCnt + 1];
        DPArr[0, 0] = 1;

        IEnumerable<PairInfoDef> PairInfoEnum = DerivePairInfoEnum(pBCnt, pWCnt);

        foreach (PairInfoDef EachPairInfo in PairInfoEnum) {
            for (int I = 0; I <= pBCnt; I++) {
                int NewI = I + EachPairInfo.BCnt;
                if (NewI > pBCnt) break;

                for (int J = 0; J <= pWCnt; J++) {
                    if (DPArr[I, J] == 0) continue;

                    int NewJ = J + EachPairInfo.WCnt;
                    if (NewJ > pWCnt) break;

                    DPArr[NewI, NewJ] += DPArr[I, J];
                }
            }
        }
        Console.WriteLine("Bが{0}個で、Wが{1}個だと、{2}通り", pBCnt, pWCnt, DPArr[pBCnt, pWCnt]);
    }

    //BとWの組み合わせの列挙を返す
    static IEnumerable<PairInfoDef> DerivePairInfoEnum(int pBCnt, int pWCnt)
    {
        for (int I = 0; I <= pBCnt; I++) {
            for (int J = 0; J <= pWCnt; J++) {
                //両方とも0個は不可
                if (I == 0 && J == 0) continue;

                PairInfoDef WillReturn;
                WillReturn.BCnt = I;
                WillReturn.WCnt = J;
                yield return WillReturn;
            }
        }
    }
}

実行結果

Bが3個で、Wが1個だと、7通り
Bが60個で、Wが40個だと、83735848679360680通り

解説

動的計画法で解いてます。