No.148

空席の数を $E = C - P$ とする.

学生が隣りあわないように並べる組み合わせの数は, まず空席を並べ, 次に学生を空席の間に(両端含む)にひとりずつ入れるようにすればいいので,

$${}_{E+1}P_{P} = (F)(F-1)(F-2)\cdots(F-P+2)(F-P+1)$$

s.t.

$$F = E + 1$$

となる. $P \geq 10^9+7$ のときは $F, F-1, F-2, \dots, F-P+1$ の中に $10^9+7$ の倍数が含まれるので答えは 0 となる.

$F \equiv G \pmod{10^9+7}$ とすると, 求める答えは

$$G(G-1)\cdots(G-P+1)$$

となり, $G-P+1 \leq 0$ のときは答えは 0 である. そうでないときは,

$$G(G-1)\cdots(G-P+1) = \frac{G!}{(G-P)!}$$

となる. 剰余の法は素数なので逆元をが求めることができる.

また, $G \lt 10^9+7$ であるが, これをそのまま計算すると間に合わないので, $10^6$ 程度ごとにあらかじめ階乗を計算しておき, ソースにその値を埋め込んでおく.