题解：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$ 的位置分类讨论：

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

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