题解：P16450 [XJTUPC 2026] 但是什么也不会改变 3

· · 题解

考虑这个限制是在干什么：对于从第三个数开始的每个数，其值必须在前两个数之间。进而，对于相邻的两个数，其后的任意一个数的值都介于它们两个之间。

我们考虑求出所有 f(n,i)。注意到限制实际上只和数之间的大小关系有关，因此有 f(n,i)=\dbinom{n}{i}f(i,i)，于是只需考虑 f(n,n) 的求法。

至此有三种做法：

  1. 注意到 1,n 一定是前两个，由对称性我们只考虑 P_1=1,P_2=n 的情形。此时 P_3 必然为 2，否则后面 2 将不会出现，进而得数列一定为：1,n,2,n-1,3,n-2\dots。于是有 f(n,n)=2。

  2. 如果注意力没那么好，可以考虑递推。显然有 f(3,3)=2。设 g(n,n) 表示 P_1<P_2 的合法情况数，则由对称性有 g(n,n)=\dfrac{f(n,n)}{2}。对于 n\ge 4，根据前面的分析，易知除去 n 后剩下的数一定构成 n-1 的情形。因此考虑在 n-1 的答案中插入 n。显然 n 只能为 P_1 或 P_2，若 P_1=n，则方案数为 g(n-1,n-1)；若为 P_2=n，则方案数也为 g(n-1,n-1)。于是有 g(n,n)=g(n-1,n-1),f(n,n)=2g(n,n)=2g(n-1,n-1)=f(n-1,n-1)，归纳可得 f(n,n)=2。

  3. 如果没有注意力，那就考虑 oeis 吧。

于是答案为 \sum\limits_{i=3}^n2\dbinom{n}{i}=2^{n+1}-n^2-n-2。代码不放了。