Codeforces Round 717 (Div.2) E - Baby Ehab Plays with Permutations の解法です． 公式解説 と同じ，というか その一部分です．
以下，次のように書きます．
- $1..n$ の順列を $S(n)$ と書く．自然に $S(n) \subseteq S(n + 1)$ とみなす．
- $S(n)$ の要素であって，ちょうど $j$ 個の互換の積で表せるものの 集合を，$X(n, j)$ と書く．
- $F(n, j) := |X(n, j)|$
問題概要
整数$n$, $k$ が与えられる． $j = 1, \ldots, k$ について，$F(n, j)$ を mod $10^9 + 7$ で求めよ．
制約: $2 \leq n \leq 10^9$, $1 \leq k \leq 200$
解法
次のように定義する．
- 順列 $p$ に対し，その互換の積の表記に現れる互換の数の最小値を $s(p)$ と書く．
- $Y(n, j) := \{p \in S(n) \mid s(p) = j \}$
- $G(n, j) := |Y(n, j)|$
すると，次が成り立つ．
$$F(n, j) = G(n, j) + G(n, j - 2) + \cdots + G(n, j \% 2)$$
$s$ の計算を考えるために， $p \in S(n) \setminus \{id\}$ のとき，$p(i) \neq i$ となる $i$ の 最大値を $i_0$ として，$p’ := p\cdot (i_0, p(i_0))$ とすると，
- $s(id) = 0$
- $p(j) \neq j$ となる $j$ の最大のものを $j_0$ として， $q := p\cdot(j_0, p(j_0))$ とすれば，$s(p) := s(q) + 1$
である．これを踏まえると，$p \in Y(n, j)$ とすると，
- $p(n) = n$ の場合は，$p \in Y(n - 1, j)$
- $p(n) < n$ の場合は，$p’ \in Y(n - 1, j - 1)$
となることがわかるから，$G$ は次のように計算できる:
\begin{align*} G(n, 0) &= 1 \\ G(n, j) &= 0\quad (n < j) \\ G(n, j) &= G(n - 1, j) + (n - 1) G(n - 1, j - 1) \end{align*}
これで答は求められるが，この計算方法では $\Omega(nk + k^2)$ なので間に合わない． そこで，$j$ が小さい時，$p \in Y(n, j)$ に対して，$p$ が動かす数は たかだか $2j$ 個しかないことに着目する．
\begin{align*} Z(n, j) &:= \{p \in Y(n, j) \mid \text{ すべての } i = 1, \ldots, n \text{ に対して } p(i) \neq i \} \\ H(n, j) &:= |Z(n, j)| \end{align*}
とすれば，
$$G(n, j) = \sum_{i = 0}^{2j} \binom{n}{i}H(i, j)$$
である．$H$ は，包除原理で求められる:
$$H(i, j) = \sum_{r = 0}^{i} (-1)^r \binom{i}{r} G(i - r, j)$$
全体として $O(k^3)$ で計算できた．