P10137 [USACO24JAN] Walking in Manhattan G

大概想到了。

考虑行走过程，从某个点向右上方行走，将这个点先固定到遇到的第一个交点，那么我们现在的问题就仅针对于这 \(n^2\) 个交点了。

考察一个很关键的事情是，假设一条直线上有 \(k\) 个交点，这 \(k\) 个交点往相反方向走所碰到的第一个改变方向的直线应当是一样的。

注意到因为是偶数，所以无论何时只需要关注第一次改变方向时的奇偶性就可以了，可以倍增处理这个过程。