Solution：AT_arc192_e [ARC192E] Snuke's Kyoto Trip

Argon_Cube · 2025-02-15 11:15:57 · 题解

这场 ARC 难度顺序是 ACEBD 吧？？？这么典的题放 E？？？

本题为 AT_agc018_e 的子集。

先考虑没有障碍物的情况。起点与终点任选比较难受，使用经典的组合意义转化为 (-1,-1)\to(n+1,m+1) 的固定起终点的路径，这样的路径去掉前两段和后两段后就可以与起点终点任选的路径对应。此时注意到只有两段或三段的路径是不合法的；原来只有一个点的路径会被算两次。所以总方案数要减去 (n+1)(m+1)+2+(n+1)+(m+1)=(n+2)(m+2)+1 才是原来起点终点任选的方案数。

接下来考虑障碍物，显然是要容斥的，我们考虑直接套用 AT_agc018_e 的方法，分别枚举进入障碍物的点和离开障碍物的点。注意实际上前两段和后两段是不包含在原问题的路径里的，所以我们需要做一些分类讨论：

1. 枚举进入障碍的点，可以算出经过障碍的格路总数。
2. 此时发现去掉前后两段后，终点在经过障碍前、起点在经过障碍后的格路是合法的，但是上面会把它们也减去，所以要加回来。
3. 此时只有三段的，无法对应到原问题的不合法格路会被多加一遍，需要减去。
4. 最后，障碍物内的、只有一个点的格路会被减两次，需要再加上。

时间复杂度 \Theta(n+m)。

Code.