数列 {an}\{ a_n \}{an} 是 {1,2,⋯n}\{1, 2, \cdots n \}{1,2,⋯n} 的一个排列,求有多少满足对于所有 1≤i≤n−11 \le i \le n - 11≤i≤n−1,均满足 ∣ai−ai+1∣≥2|a_i - a_{i + 1}| \ge 2∣ai−ai+1∣≥2 的排列。
请问有没有多项式复杂度的解法?
谢谢大佬们!