No.147

$i$ 個の椅子に座ることのできる組み合わせの数を $E_i$ として, $i$ 番目の椅子に座っていない場合の組み合わせの数を $F_i$, $i$ 番目の椅子に座っている場合の組み合わせの数を $G_i$ とすると,

$$\begin{align*} E_i &= F_i + G_i \\ F_i &= E_{i - 1} \\ G_i &= F_{i - 1} \end{align*}$$

となり,

$$E_i = E_{i - 1} + F_{i - 1} = E_{i - 1} + E_{i - 2}$$

となる. これはフィボナッチ数列である.

このとき, すべての組み合わせの数は,

$$\prod (E_{C_k})^{D_k}$$

となる. 今回は $C_k$ が大きいので $E_i$ を求めるために行列を使う.

$$A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$$

とすると,

$$\begin{pmatrix} * \\ E_i \end{pmatrix} = A^n \begin{pmatrix} 0 \\ 1 \end{pmatrix}$$

となり, 累乗の計算は $a^8 = a^{ {2^2}2 }$ のように高速化できる.

さらに, 今回は $D_k$ も大きいが, 剰余の法が $p = 10^9 + 7$ で素数であるので, フェルマーの小定理から

$$a^{p - 1} \equiv 1 \pmod p$$

となるので, $D_k$ を $p - 1$ で割った余りだけ累乗すればいい.