复杂做法

· · 题解

根据 F1 的结论,我们要统计满足如下条件的长度为 n 的排列 p 的数量:

  1. 题目钦定了 p 中某些位置的值。

  2. p_1>p_2 的假设上,p_1,p_3,\cdots 形成单峰,p_2,p_4,\cdots 形成单谷。在 p_1<p_2 的假设上则反之。

如图 A,我们将位置 1-3-\cdots-4-2-1 连成一个环,然后在值 1 的位置(即 p_2,p_4,\cdots 的谷的位置)确定后(如图中标注),依次填入值 2,3,\cdots,n 得到 p,该过程中当前填了的位置在环上应该是包含值 1 位置的一段(如图中用红色圈住的一段)。

那么这个填数过程可以理解成 n-2 次 “将当前要填的数填在当前段左端/右端” 的选择。如果用二维网格图来表述,就是一条从 (0,0) 走到 x+y=n-2 上一点的折线路径,只允许向上(填左端)和向右(填右端)。

事实上,在这种理解下,我们已经保证了第三个限制条件,现在来考虑第二个限制条件。

如图 B,我们将第二个限制条件用一些有向边表示(小指向大)。讨论后发现,无论值 n 落在哪,结合第三个限制条件,可以将图 B 的限制化简得到图 C(图 C 中外围的那条标有 a 的有向边不是大小关系限制,而是描述这条有向边囊括的这段长 a。下面图 D、图 E 同理)。

现在考虑这些有向边带来的限制。如图 C,以值 1 位置左边的第一条有向边为例,它要求左侧在走第一步前,右侧不能走超过 a 步,即当 x=0 时始终有 y\leq a。同理,值 1 位置左边的第二条有向边要求 x=1 时始终有 y\leq a+1。那么我们可以将这些要求看作折线不能越过 y=x+a。(注意当 x 超过 1 左边的有向边数时,y 此时理论上应当是没有限制的,但是若此时 y 超过了 x+a,容易发现就会有 x+y>n-2,这本身就是不合法的)而值 1 位置右边的有向边相当于要求折线不能越过 y=x-(n-a-1)

再考虑第一个限制条件。若我们钦定了某偶数位置的 p_i=v,如图 D。不妨设 i 在值 1 位置左侧,设值 1 位置到 i 共需填 x 个数。那么这相当于我们在填入数 v 前,段的左侧应当恰好填了 x-1 个数、右侧应当恰好填了 v-2-(x-1) 个数,也就是要使得折线经过点 (x-1,v-2-(x-1))。该点在 x+y=v-2 上。

否则,若我们钦定了某奇数位置的 p_i=v,如图 E。但由于 n 的位置不确定,我们不知道 i 到底是从段的左侧被加入的还是从段的右侧被加入的,所以两种情况都要考虑到。具体地,设从左侧加入的话需要加入 x 个数才到 i,那么类似刚才的分析,若从左侧加入,要求经过点 (x-1,v-2-(x-1));若从右侧经过,要求经过点 (n-x-1,(v-2)-(n-x-1))。这两个点都在 x+y=v-2 上。

整理一下限制。如图 F,现在要求从 (0,0) 走到 x+y=n-2 上的任意一点,其中不能越过 y=x+ay=x-(n-a-1)。同时,对于某些 x+y=k,我们要求必须在该直线上的某一点/某两点处越过该直线。由于走的过程中 x+y 是单增的,所以我们直接按这些限制直线 DP 即可(设 f_{i,1/2} 表示走到了第 ix+y=k 的限制直线上的第 1/2 个点上的方案数,当然如果只有一个点就不需要 f_{i,2})。

过程中需要求从一点走到另一点且不越过 y=x+ay=x-(n-a-1) 的方案数。相当于不要进入两个限制区域内,而注意到,从左上的限制区域移动到右下的限制区域内,横坐标至少要增大 a+(n-a-1)=n-1,而我们至多走 n-2 步,所以不可能存在一条路径同时进入了两个限制区域。此时的路径方案数是好算的,只需用总方案数减去单独进入每个限制区域的方案数即可,可以 O(1) 计算。

然后考虑值 1 位置的可能范围。注意到,若我们将所有在偶数位置钦定的 p_i 提出,并设其中最小的那个为 p_b,其左侧、右侧最近钦定的偶数位置分别为 p_a,p_c,如图 G,那么值 1 位置就只可能在 (a,b) 间或 (b,c) 间,对两种情况分别计算。一种情况内,发现值 1 位置从 o 移动到 o-2 时,相当于平面上整个图案向左上移动了一格,但是起点 (0,0) 没变成 (-1,1)。所以,我们找到第一条限制直线 x+y=k,然后把它之后的方案数先预处理出来,那么对每个 o 就只需要计算 (0,0) 到这条直线上一点/两点的方案数了,这个按照上一段说的 O(1) 计算即可。

但注意这里,若没有任何限制直线,我们就找不到第一条 x+y=k,此时相当于多次求 (0,0)x+y=n-2 且不经过 y=x+ay=x-(n-a-1) 的方案数。仍然考虑用总方案数减去单独进入每个限制区域的方案数。总方案数形如 \sum_{x=l}^r\binom{x+y}{x},注意到 x+y=n-2 是固定的,于是预处理组合数前缀和即可 O(1) 求值。而减去的方案数需要将 (x,y) 对称到形如 (A-x,B-y) 的点,那么贡献形如 \sum_{x=l}^r\binom{A-x+B-y}{A-x},同样也是预处理组合数前缀和。

综上我们就得到了 O(n) 的做法。做法可能复杂了些。代码咕了,但做法的正确性大致没问题(