在硬盘里翻到了当时没推完的这个题，今天补完了最后几步。
题目链接：https://hydro.ac/d/bzoj/p/4321
对任意相邻两个元素差的绝对值不为 \(1\) 的 \(n\) 阶排列计数。
\(\mathcal{O}(n^2)\) 做法是考虑按照值域由小到大逐步插入，记录 \(f_{i,j}\) 为长度为 \(i\) 的排列，一共有 \(j\) 对冲突的。每次考虑插入下一个数，发现还要记录一维当前 \(i\) 和 \(i-1\) 是否相邻这个信息，然后就能转移了。
然后下面是 \(\mathcal{O}(n)\) 的做法。
首先考虑容斥，首先将排列划分成若干极长的值域连续段，如果一段长度为 \(1\) 那么其容斥系数为 \(1\)，否则长度为 \(k\) 的连续段容斥系数为 \(2\times (-1)^{k-1}\)，这里要乘 \(2\) 是因为有上升和下降两种方式。考虑其 OGF \(F(x)=x-2x^2+2x^3-2x^4+\cdots=x(\frac{2}{1+x}-1)=x\frac{1-x}{1+x}\)，枚举一共有 \(n\) 段，即得答案的 OGF \(H(x)=\sum_{n\geq 0}x^n(\frac{1-x}{1+x})^n\)，首先如果令 \(G(x)=\sum_{n\geq 0}n!x^n\)，其为超几何函数，微分有限，而 \(F\) 是代数形式幂级数，从而 \(H=G(F)\) 微分有限，存在整式递推。
手算一下！
凑出这个之后，将 \(F(x)\) 代入 \(x\)，然后整体乘 \(F'(x)=\frac{\mathrm{d}F(x)}{\mathrm{d}x}\) 把 \(H'\) 凑出来。
其中 \(F(x)=x\frac{1-x}{1+x},F'(x)=-\frac{x^2+2x-1}{(1+x)^2}\)，代入进去并整理可得：
\(n\geq 4\) 时左右两边提取 \([x^n]\) 可得：
即得整式递推：
代码。