题解：CF1967E2 Again Counting Arrays (Hard Version)

· · 题解

直接容斥，用总数量减去不合法的数量。

考虑将题目转化为一个格路计数问题：(i,a_i) 位置禁止经过，判定是否存在一条从 (0,b) 出发，每次从 (x,y) 走到 (x+1,y\plusmn 1) 的位置能否走 n 步。

首先对于判定问题，我们显然会优先向 (x+1,y+1) 走，并且一旦碰到 y=m 这条线就寄了。所以能让我向上走有 m-1 种方法，但是让我向下走只有 1 种方法。

直接暴力 dp 就可以做到 O(nm)。

枚举碰到 y=-1 这条线的时刻 t，则 t 之前的路径不能碰到 y=m 和 y=-1 两条直线，可以使用类似 P3266 的反射容斥做到 O\left (\frac {n^2} m\right )。

根号分治一下，我们得到了一个 O(n\sqrt n) 复杂度的做法，可以通过 E1，code。

暴力 dp 没有前途，考虑延续反射容斥的做法。我们能不能不去枚举碰到 y=-1 的时刻呢？

其实是可以的。你注意到碰到 y=-1 之后我们仍然需要在后面乱填，需要乘上 m^{n-t} 的贡献，而这等价于碰到 y=-1 之后开始随便乱走。这样我们只要枚举终点的位置 p 即可。设 (0,b)\to (n,p) 往上走了 k 次，则贡献为 (m-1)^k，这样我们只需要计算有多少条合法的路径即可。

定义一条路径合法，当且仅当它第一次碰到的边界是 y=-1。考虑对 p 的位置分类讨论：

  1. 如果 p\le -1，则显然你一定会碰到一次 y=-1，但不一定是第一次碰到。所以需要减去先碰到上边界的方案数，然后加回先碰下再碰上的方案数……反射容斥即可。
  2. 如果 p>-1，则我们可以先把碰到 y=-1 之后的部分翻转下来，转化为 p\le -1 的问题。

我们发现，一个位置 p，往上反射后到达 2m-p，再往下反射会到达 p-2m-2。也就意味着，能对原本的 p_0 造成贡献的位置在 y=-1 下方和 y=m 的上方形成了两个公差为 2m+2 的等差数列，可以用类似差分的方式维护。

最后扫一遍值域还原回去。复杂度线性，code。