Roaming [AtCoder Beginner Contest 156 E]

https://atcoder.jp/contests/abc156/tasks/abc156_e

前提知識

• mod上での二項定理

解説

https://atcoder.jp/contests/abc156/submissions/10312260

どこから手を付ければよいか分からなかったかもしれない。
今回数えたい組み合わせは、手順ではなく最終的な状態である。
どのような条件を満たせば作成可能で、それが何通りあるかを数えよう。

具体的には以下の条件を満たせば、作ることができる。
- 人数の合計が合計N人
- 人が誰もいない部屋がK個以下
この仮定を導き出すのが難しい。

人が誰もいない部屋という条件が少し特殊なので、これを全探索して数え上げていこう。
誰もいない部屋がzero個で、残りの部屋でN人を振り分ける組み合わせは、
C(N, zero) * H(N - zero, N - (N - zero))
となる。
C(N, zero)は誰もいない部屋をどう選ぶかの組み合わせ
H(N - zero, N - (N - zero))がN人を残りでどう置くかの組み合わせ。
もう少し細かくすると、N - zeroは人を配置する部屋の個数で、
N - (N - zero)は、実際に配分する人数であり、N個から(N-zero)を引いているのは、
(N - zero)個分の配置する部屋があり、そこには1人すでに配置しておくためである。

int N, K;
Comb<mint, 401010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    chmin(K, N - 1);

    mint ans = 0;
    rep(zero, 0, min(K + 1, N)) ans += com.aCb(N, zero) * com.nHk(N - zero, N - (N - zero));
    cout << ans << endl;
}