题解：AT_agc077_e [AGC077E] Hamiltonian Path Inversion

· · 题解

给一个 \max=999999，做法来自 gblaasnicse 大神，磕一个。据说没办法取满 0\sim 10^6？

黑表示 0，白表示 1，则我们构造这样的图： 那么有 1001 个黑格，999 格白格，因此逆序对数上界就是 999999。将路径 reverse 可以把逆序对数 N 变成 999999-N，所以不妨 0\leq N\leq 499999。

我们希望有一个较为普遍的构造，所以 corner 情况先判掉： 上图构造可以解决 0\leq N<500，下面讨论的 N 同时有不错的上下界 500\leq N\leq 499999。下面构造只要自由度足够多，我们有理由相信 N 可以取遍 [500,499999] 任何数。 这部分是第一个自由度，从右侧出来后，我们希望第一步走到 (1,b)。这里我们令 b=a 或者 b=a-1（我画的例子中 b=a-1，只是为了保证后续可能的奇偶性问题）。a 对应 2(W-a) 个开头的白格，是一个二次的量（大步）。 画出 b 之前的路线，那么逆序对数的式子是：

N=A-1+(2B-1)(C-B+1)

这里要求一下 2\leq A<B<C\leq b 且 b-C,C-B+1,A-B+1 都是 2 的倍数即可。

有足足 3+1=4 个自由度，解方程就非常轻松了，代码可以参考这里。