ABC156 - E - Roaming - Senの競技プログラミング備忘録

概要

n個の1~nまで番号がついてる部屋があって、それぞれ1人ずついる。ある部屋にいる一人が別の部屋へと行く行動をアクションと呼ぶ。
アクションがちょうどk回行われたときに、それぞれの部屋にいる人の数の組み合わせの数を10^9+7で割ったあまりで答えよ。

制約：　3 <= n <= 2 * 10^5, 2 <= k <= 10^9

ACするまで

1. kがやたらと大きいので、本当にk回シッカリ動かす必要があるのか？
2. ないです。(n, 0, 0, ..., 0)のようなパターンを作るのに最大でn - 1回しかかからないので、あまり大きい場合は何人かの人が部屋A->部屋B->部屋Aのように、反復運動をやればよさそう。
3. 動かす回数kを固定して、考えてみる。->わからないな

4. 0にする部屋の数を固定してみる。
5. そうすると、残りの部屋で和がnになるように、部屋の人数を振り分けることになる。
6. 丁寧に組み合わせを考えて、AC！

考察

for me:
今回の問題の敗因としては、最初に決める方針が間違ったせいできれいに詰められなかったことであるが、その根底には、一度決めた方針を考え直しづらいことが根底にあると思う。その原因は、数学力(特に組み合わせについて)に自信がないため、どの方針が正解なのかがわからないのが原因だと思う。この休みの間に、組み合わせについて特訓しようと思う。

a回動かしてたどり着ける盤面！とやろうとすると、次のような条件を満たすものを数え上げることになる。
$x_1+x_2+..x_n=n, 0 \leq x_i$ で、ちょうどa回の移動後。
ぼくにはa回移動後を上のような数式で表す方法は知らない

Point
DPじゃなくて数学系でやる組み合わせ問題は、とにかく固定する要素を挙げて、それを確かな数学力のもとで実行可能かを確かめる。

今回の場合は、「 $x_i$ のうち0と等しい個数」を考える。
0の個数に関しては、最大ではn-1個((n, 0, ..., 0)を作るとき)である。
0の個数をa個とすると、0でない要素はn - a個存在することになる。それらは、n - a個の0でない要素の並び方は、
$x_1+x_2+...+x_{n-a}=n, x_i \ leq 1$ を満たすような $(x_1, x_2, ..., x_{n-a})$ の組み合わせの数と同じ(重複組み合わせ)。
また、今回は0個であるものがa個存在するので、次のように考えると答えが見える。