考虑容斥，设
fk 为有恰好
k 个位置满足
∣ai−ai+1∣=1，则有
fk=[xn]∑i=0n(ki)(−1)i−k(n−i)!(1−xx+x2)n−i
设
fk 的生成函数为
F(t)，则有
F(t)=[xn]∑i=0n(t−1)n−ii!(1−xx+x2)i
为了分析其结构，再设
G(t)=∑i=0ntiii
运用
经典方法 可知
G(t) 是微分有限的，所以
F(t)=(t−1)nG((t−1)−1)
显然也是微分有限的。
但是手动计算整式递推式可能比较复杂，建议暴力计算若干项后，直接使用高斯消元来找出整式递推式。整式递推式在边界处可能会爆掉，需要注意一下。
孩子们我的
Θ(n) 做法没肘赢神秘匿名用户。