前置知识

你可能需要了解一些生成函数基础。应该可以先看，看不懂再去学。

约定

\(F\) 表示函数，\(f\) 表示一个生成函数（一个拥有无限项的多项式？）。

\([x^i]f\) 表示多项式 \(f\) 的 \(x^i\) 的系数。

函数 \(\to\) 普通生成函数封闭形式

如果有这样一个函数

\(G(i)\) 是什么呢，是长为 \(i\) 的合法置换环的个数：

• 合法置换环：只有一个置换环且是由从 \(1\) 升序到 \(n\) 再从 \(n\) 降序到 \(1\) 的两条链构成的。

如果我们要求 \(F(n)\) 为长为 \(n\) 的序列满足：

• 由合法置换环构成（此处是由 \(mn\to mx, mx\to mn\) 的两条链构成的）
• 每个置换环都是序列上连续的一段区间。

那么 \(F(n) = \sum\limits_{i = 1}^{n}F(n - i)G(i), F(0) = 1\)。

那么写出生成函数 \(g = \sum\limits_{i = 0}G(i)x^i = x + \sum\limits_{i = 2}2^{i - 2}x^i = x + x^2\sum\limits_{i = 0}(2x)^i = x + x^2\frac{1}{1 - 2x} = \frac{x^2 + x(1 - 2x)}{1 - 2x} = \frac{x - x^2}{1 - 2x}\)。

然后考虑一个合法排列相当于若干个合法置换环拼接起来，有 \(f = \sum\limits_{i = 0}^{n} g^i\)，即枚举由几个置换环拼接而成。那么 \(f = \frac{1}{1 - g} = \frac{1 - 2x}{1 - 3x + x^2}\)。

普通生成函数封闭形式 \(\to\) 递推方程

这里我们需要求出 \([x^n]f\) 即为答案，那么这里怎么求呢？

我们考虑设 \(f = a_0 + a_1x + a_2x^2 +\dots\)（其中实际上有 \(a_i = G(i)\)）

对于 \(f\)，\(f = \frac{1 - 2x}{1 - 3x + x^2}\) 等价于 \((1 - 3x + x^2)f = (1 - 2x) = t\)，左侧的 \(=a_0 + (-3a_0 + a_1)x + (a_2 + -3a_1 + a_0)x^2 + \dots\)，所以我们其实得到了关于 \(a\) 的方程组。

还发现对于 \(i\ge 2\)，有 \([x^i](1 - 2x) = 0\)，且 \([x^i]\ ((1 - 3x + x^2)f) = 1(a_ix^i) + (-3x)(a_{i - 1}x^{i - 1}) + x^2(a_{i - 2}x^{i - 2}) = (a_i -3a_{i - 1} + a_{i - 2})x^i = [x^i](1 - 2x) = 0\)。

于是我们实际上得到了关于 \(F(i)\) 的递推式，在本问题中 \(F(0) = F(1) = 1, F(i) = 3F(i - 1) - F(i - 2)(i\ge 2)\)