ARC067 E - Grouping

問題文

http://arc067.contest.atcoder.jp/tasks/arc067_c

解法

dp[i + 1][j] := i 人以下のグループのみを用いて，あと j 人グループ分けされてない人がいるときの場合の数
という dp で解けます．
遷移は，use == 0 または C <= use <= D のとき
$$\displaystyle dp[i + 1][j - use \times i] = dp[i][j] \times \frac{_jC_i \times _{j-i}C_i \times \ldots \times _{j-(use-1)\times i}C_i}{(use)!}$$
になります．これは，j 人から i 人を選ぶ，という操作を use 回繰り返すが，グループ自体の区別はつけないので，グループの順列で割るということです．

ソースコード

#include <bits/stdc++.h>
using namespace std;

// mod は略

int main() {
    int N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    vector<vector<mod>> dp(B + 2, vector<mod>(N + 1));
    dp[A][N] = 1;
    for(int i = A; i <= B; ++i) {
        for(int j = 0; j <= N; ++j) {
            if(dp[i][j] == 0) {
                continue;
            }
            mod t = dp[i][j];
            for(int use = 0; use * i <= j; ++use) {
                if(use == 0 || C <= use && use <= D) {
                    dp[i + 1][j - use * i] += t * fact<MOD>(use, false);
                }
                t *= comb<MOD>(j - use * i, i);
            }
        }
    }

    cout << (int)dp[B + 1][0] << endl;
}

感想

数え上げる問題が苦手すぎる．中学高校で訓練しておけばよかった…．