Solution：AT_arc202_d [ARC202D] King

省队集训原题。场上一眼秒了。

根据省集原题，显然我们可以把 $x$ 方向与 $y$ 方向的移动拆开。但是我们发现题目里要求我们不能待在原地不动，这个没有任何问题，我们直接容斥有几步是原地不动的就完事了。

令 $f(n,m,a,b)$ 为：从 $a$ 出发，走 $m$ 步到达 $b$，每步可以从 $x$ 移动到 $x-1,x,x+1$，要求移动过程中不能超出 $[1,n]$ 的方案数。现在我们需要对于每个 $0\leq t\leq T$ 求出 $f(N,t,A,C)$ 与 $f(M,t,B,D)$，这样移动至多 $t$ 步的方案 $f_t$ 就是这两个乘起来。

现在我们考虑怎么求 $f(N,t,A,C)(0\leq t\leq T)$，同样把原题的根号分治套过来，当 $N\leq\sqrt T$ 直接 $\Omicron(NT)$ 暴力 DP，否则直接 $\Omicron\left(\dfrac {T^2}N\right)$ 对于每个 $t$ 折线容斥。

但是我们只会每次走到 $x+1,x-1$ 的折线容斥，现在可以不动了怎么办？直接枚举有 $k$ 步留在原地，剩下 $t-k$ 步的方案数 $g_{t-k}$ 就可以折线容斥，然后我们发现 $f(N,t,A,C)=\sum_{i}\binom tig_{t-i}$，所以直接卷就完事了。

最后简单容斥一下，答案是

注意容斥系数只有 $(-1)^{T-i}$，组合数实际上是在枚举有哪几步原地不动。

但是官方题解是 $\mathrm O(T\log^2 T)$，怎么回事呢！

考虑优化求 $f(N,t,A,C)$。用 ABC309Ex 的多项式方法做反射容斥，这样通过一些简单的转化，我们就只需要解决对于 $0\leq t\leq T$ 求 $[x^0]x^A(x^{-1}+1+x)^t$ 了，其中卷积是 $\mod x^{2N+2}-1$ 意义下的循环卷积。

考虑分治，如果我们想求 $l\leq t\leq r$ 的答案，我们可以在分治过程中先顺便求出 $x^A(x^{-1}+1+x)^l$。此时我们发现除了 $x^{-(r-l)}$ 到 $x^{r-l}$ 的项以外都是没用的，所以需要保留的项数与分治区间长度同阶。

这样就做到了 $\Omicron(T\log^2 T)$。但是显然这是跑不过 $\Omicron(T^{1.5})$ 的，事实上据 Kapt 的提交前者的用时是后者的 $10$ 倍以上。