ABC156 E. Roaming

問題

n個の部屋があり、最初各部屋には1人ずついる。
ここで、ある部屋iから別の部屋j (i != j)へ移ることを「人の移動」と呼ぶことにする。
人の移動がk回起きたことがわかっているとき、各部屋にいる人数の組合せとして何通りあり得るか、10^9+7で割ったあまりを答えよ。

制約

• 3 <= n <= 2*10^5
• 2 <= k <= 10^9

解法

まず、どのような状態が答えとしてありえるか？を考える。
k回移動なので、部屋の中で0人の部屋の数は0～min(N-1, K)だけありえる。
また、例えば、「m回移動があった部屋の状態」も、k-m回適当にどこかの部屋にいた人を移動させ、そこからm回動かすことでk回移動での答えになりえる。(調整可能)
したがって、「k回以下の移動のすべての部屋の状態(ある部屋の状態への最小の移動回数がk回以下がすべて)」が答えになり得る。

上記で、ぴったりk回移動を考えなくてよく、k回以下で達成できる部屋の状態を考えれば良いことがわかったので、k回以下の移動で条件を満たす組み合わせを考える。

各部屋の状態は、0人の部屋と1人以上の部屋がありえている。
ここで、0人の部屋の数がp(<=k)部屋あった場合、p人が残りのN-p部屋のいずれかに行っていることになるが、これはすべてk回以下の移動なので、すべて条件を満たす移動になっている。
この組合せは、0人の部屋のp部屋の組合せ「N_C_p」とp人がどの部屋に行くかの組合せ「(N-p)_H_p」から「N_C_p * (N-1)_C_p」で求められる。

メモ

• k回ぴったり→k回以下
• 「減る」「増える」が混ざっている→片方を固定して考える
  • 最終的に0人＝1回減るだけ、または、減る＋１＝増える　→　1回減るだけ考えればよい
  • 最終的に1人以上＝移動なし、または、減る＜＝増える　→　0回以上増えるだけ考えればよい