Solution：AT_arc202_d [ARC202D] King

Argon_Cube · 2025-07-21 19:48:41 · 题解

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

根据省集原题，显然我们可以把 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}，组合数实际上是在枚举有哪几步原地不动。

Code.

但是官方题解是 \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 倍以上。