AOJ 2333 : 僕の友達は小さい My friends are small (JAG Summer 2010)

まずは簡単な例外的な組合せから数えてみる。以下、解をanswerと表記する。どの友達もリュックに入れることができないならばanswer+=1。また、すべての友達をリュックに入れることができるならばanswer+=1。

それ以外の場合を数える。とりあえずリュックに入れない友達の最小の重さmを総当たりにより固定する。これはたかだかN通り。このとき重さm未満の友達はすべてリュックに入るはずだから、少なくともの重さの友達をリュックに入れる。さて、注意しなければいけないのは、重さmの友達が１人とは限らないことである。重さmの友達の人数をと表記することにする。重さmの友達を人選ぶ方法は通りである。このとき重さの和は、重さm未満の友達も考慮に入れるとである。

mごとにDPを解く。

dp(i, j) := 「重さi-1の友達の状態まで確定した時、リュックに入った友達の重さの和がjである。そのような場合の数」

とする。 これを先のによってDPを初期化してから計算していく。重さmの友達が入れられない状態のみを計算するので とする。

計算量は全体でO(WN²)

vector<vector<int>> combinations(int n, int mod) {
    auto res = vector<vector<int>>(n + 1, vector<int>(n + 1));
    rep(i, n + 1) res[i][0] = 1;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= i; ++j)
        res[i][j] = (res[i - 1][j - 1] + res[i - 1][j]) % mod;
    return res;
}

int N, W, wt[201], M;
vector<vi> C;
vector<pii> we;
mint dp[201][10001];

mint f(int s) {
    int mi = we[s].first;
    FOR(i, s + 1, M) {
        int w, num;
        tie(w, num) = we[i];
        rep(j, num + 1) {
            rep(k, W + 1) {
                if (j*w + k <= W) {
                    dp[i + 1][j*w + k] += dp[i][k] * C[num][j];
                }
            }
        }
    }
    mint re;
    FOR(i, 1, W + 1) {
        if (mi > W - i)re += dp[M][i];
    }
    return re;
}

int main() {
    C = combinations(200, 1000000007);

    cin >> N >> W;
    rep(i, N) {
        cin >> wt[i];
    }
    sort(wt, wt + N);

    int pre = -1;
    rep(i, N) {
        if (wt[i] != pre) {
            we.push_back(mp(wt[i], 0));
        }
        we.back().second++;
        pre = wt[i];
    }

    mint re;
    M = sz(we);
    int sm = 0;
    rep(i, M) {
        MEM(dp, 0);
        int num = we[i].second;
        rep(j, num) {
            if (sm <= W) {
                dp[i + 1][sm] += C[num][j];
            }
            sm += we[i].first;
        }
        re += f(i);
    }
    if (sm <= W)re += 1;
    if (wt[0] > W)re += 1;
    cout << re << endl;
}