チーム分け [Mujin Programming Challenge 2018 F]

https://beta.atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f

解法

https://beta.atcoder.jp/contests/mujin-pc-2018/submissions/2947875

chokudaiさんの解説放送が良質すぎる
公式解説
以上の副読本としての解説。
　
DPで解く。
解説放送にあるようにサイズの大きいグループから確定させていこう。
dp[team][rest] := サイズteamまで作っていて、確定待ちの人数がrest人のときの組み合わせ数
dp[1][0]が答えになる。
DPをするために別途配列Bを作る。
B[i] := aj=iである人数
　
dp[team][rest]からdp[team-1][rest-確定人数]へ遷移させていくが、確定人数の方は1グループ作る2グループ作るなど、
遷移先のrestが0未満にならないようにサイズがteam-1のグループを作ることができるので、遷移がO(1)にならない。
慣れないと以下のプログラムはO(N^3)に見えるのだが、実際はO(N^2logN)である。
これはエラトステネスの篩で見られる計算量見積もりである
以下のプログラムでは逆数を求めるのに計算量にlogが更に付くが、ACできる。

int N, A[1010], B[1010];
mint dp[1010][2010];
Comb<mint, 2020> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) B[A[i]]++;

    dp[N + 1][0] = 1;
    rrep(team, N + 1, 2) rep(rest, 0, N + 1) if(dp[team][rest].get()) {
        int team2 = team - 1;
        int rest2 = rest + B[team2];

        for (int i = 0; i*team2 <= rest2; i++) {
            dp[team2][rest2 - i * team2] += dp[team][rest] * com.aPb(rest2, i * team2) * com.ifac[i] / (com.fac[team2] ^ i);
        }
    }

    cout << dp[1][0] << endl;
}