P13909：A001100

· · 题解

出 OEIS 题好玩吗？

考虑容斥，设 f_k 为有恰好 k 个位置满足 |a_i-a_{i+1}|=1，则有

f_k=[x^n] \sum_{i=0}^n\binom ik (-1)^{i-k} (n-i)! \left( \frac{x+x^2}{1-x}\right)^{n-i}

设 f_k 的生成函数为 F(t)，则有

F(t) =[x^n]\sum_{i=0}^n (t-1)^{n-i} i! \left( \frac{x+x^2}{1-x}\right)^i

为了分析其结构，再设

G(t)=\sum_{i=0}^n t^i i! [x^n]\left( \frac{x+x^2}{1-x}\right)^i

运用 经典方法 可知 G(t) 是微分有限的，所以

F(t)=(t-1)^n G((t-1)^{-1})

显然也是微分有限的。

但是手动计算整式递推式可能比较复杂，建议暴力计算若干项后，直接使用高斯消元来找出整式递推式。整式递推式在边界处可能会爆掉，需要注意一下。

孩子们我的 \Theta(n) 做法没肘赢神秘匿名用户。