問題

$N$ 個のマスがあり白く塗られている。ある操作で $i, i+1$ を黒く塗ることができる。順列 $P(1, 2, ..., N-1)$ によってすべてのマスを黒く塗るとき、はじめてすべてのマスが黒く塗られるまでの回数 $k$ が何通りあるかそれぞれ求めよ。

制約

$2 \leq N \leq 10^6$

何が簡単に求めることができるだろうか。条件を緩めて求めやすい数はないか？という意識で方針を探索することが重要。

ちょうど $k$ 回の操作ですべてのマスが黒くなる場合の数を数えると、 $k-1$ 回までは少なくとも $1$ つのマスは白くなっており、 $k$ 回目の操作ですべて黒くなる場合を考えなければならない。これは数えにくい。

ちょうど $k$ 回で塗る場合の数ではなく、 $k$ 回以下ですべて塗る場合の数を考えると $k-1$ 回以下ですべて塗られている場合も含めて $k$ 回ですべて塗られていればよいので、数えやすくなる。 $k$ 回以下ですべてのマスを塗る場合の数が何通りにあるか求める。

$k$ 回以下で塗るときの必要条件は、

(A). $1, n-1$ は $k$ 回の中に必ず含まれる
(B). ( $a_1 \lt a_2, ..., \lt a_{n-1}$ として) $1 \leq a_i - a_{i-1} \leq 2$

である。((B). によって順列の対象となる数が決まるイメージ)

(A). については $1$ 通りである。(B). については $a_i - a_{i-1} = 1$ となる回数を $a$ 、 $a_i - a_{i-1} = 2$ となる回数を $b$ とすると以下が満たされる必要がある。

上記を満たす $a$ 個の $1$ 、 $b$ 個の $2$ の順列、 $a_1, a_2, ..., a_{n-1}$ である $k$ つの数の順列, それ以外の $n-1-k$ つの順列の積が $k$ 回以下ですべてのマスを塗る場合の数となる。

あとは、ちょうど $k$ 回の場合の数 = $k$ 回以下の場合の数 - $k-1$ 回以下の場合の数であるから、求めることができる。