TopCoder SRM584 Div2 Hard Excavastions2

概要

遺跡発掘？ 何種類かのn個の建物があり、K個選ぶ。選んだ建物の種類一覧が与えられる。選び方は何通り？

サンプル

建物:{1, 2, 2, 1}
種類:{1, 2}
数:2
1, 2, 2, 1の中から2個選び出したら、1と2が入っていた(つまり1と2だった)選び方は？
もちろん(1の選び方)*(2の選び方)=2*2=4

建物:{1, 2, 2, 1}
種類:{1}
数:2
2個選んだら、1のみが入っていた
つまり両方1だったという事なので1通り

制約

建物の種類は1~50
1≦n≦50 1≦k≦n

解法

DP
d[i][j]:i番目までの種類でk個選ぶ選び方
d[i][j] = Σ(dp[i-1][j-k]*b[i]Ck):(k=1~min(b[k], j))
ただしb[i]は種類がiの建物の数

ソースコード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>

using namespace std;
typedef long long ll;

class Excavations2 {
    ll dp[52][52];
    ll comb[52][52];
    public:
    long long count(vector<int> kind, vector<int> found, int K) {
        for (int i = 0; i < 52; i++) {
            for (int j = 0; j < 52; j++) {
                if (j > i) comb[i][j] = 0;
                else {
                    ll result = 1;
                    for (int l = 1; l <= j; l++) {
                        result *= i - l + 1;
                        result /= l;
                    }
                    comb[i][j] = result;
                }
            }
        }
        std::vector<int> b;
        for (int i = 0; i < found.size(); i++) {
            b.push_back(std::count(kind.begin(), kind.end(), found[i]));
        }
        for (int i = 1; i <= K; i++) {
            if (i > b[0]) dp[0][i] = 0;
            else dp[0][i] = comb[b[0]][i];
        }
        for (int i = 1; i < b.size(); i++) {
            for (int j = 1; j <= K; j++) {
                dp[i][j] = 0;
                for (int l = 1; l <= b[i]; l++) {
                    if (j < l) break;
                    dp[i][j] += dp[i-1][j-l]*comb[b[i]][l];
                }
            }
        }
        return dp[b.size()-1][K];
    }
};