【题解】洛谷 P6657 【模板】LGV 引理

wsyhb · 2021-07-27 21:42:29 · 题解

前言

为了使文章更加简洁，本文省略了有关 LGV 引理的定义，若有需要请前往 LGV 引理 - OI Wiki 以了解定义。

证明

先把 LGV 引理的式子写出来：

即

（其中 p 为 1 到 n 的排列）

等式左边相当于选 n 条起点和终点分别互不相同的路径——设第 i 个起点对应的是第 p_i 个终点，若 p 逆序对个数为偶数则系数为 1，否则系数为 -1。

等式右边几乎完全一样，只是多了 n 条路径互不相交的限制。

因此，我们考虑存在路径相交的情况（此处路径相交不包括：起点或终点相同），可以发现：每一个偶数个逆序对的方案，与另一个奇数个逆序对的方案一一对应。

对应方法有很多种，此处举个例子：

对于一个存在路径相交的偶数个逆序对的方案，选出其中与其他路径相交的起点编号最小的路径 x，再选出与 x 相交的起点编号最小的路径 y，然后选出 x 和 y 的公共点中最靠近终点的点 p，将 p 到两个终点之间的部分互换，那么逆序对个数会变成奇数。

因此引理得证。

交换排列中的两个值，逆序对个数奇偶性会不同的证明：

设排列为 p，交换的位置编号为 x 和 y，其中 x<y，则 p_x,p_y 与另外某个数 p_i 贡献的逆序对个数有以下几种情况：

• 对于 i<x 或 i>y，p_i 与值 p_x,p_y 的相对位置在交换前后均未改变。
• 对于 x<i<y
  • 若 p_i<p_x,p_y 或 p_i>p_x,p_y，则 p_i 与 p_x,p_y 贡献的逆序对个数在交换前后均为 1。
  • 若 \min(p_x,p_y)<p_i<\max(p_x,p_y)
    • 若 p_x<p_y，则 p_i 与 p_x,p_y 贡献的逆序对个数交换前后分别为 0,2。
    • 若 p_x>p_y，则 p_i 与 p_x,p_y 贡献的逆序对个数交换前后分别为 2,0。

上述情况奇偶性均未变化，且 p_x 和 p_y 之间贡献的逆序对要么从无到有，要么从有到无，证毕。

题解

注意到条件 a_1 \le a_2 \le \cdots \le a_m 和 b_1 \le b_2 \le \cdots \le b_m，这说明只要路径不相交就一定有 (a_i,1) 对应的终点是 (b_i,n)。

因此所有不相交路径方案的系数恒为 1，直接套用 LGV 引理即可。