转化一下,每天走过的总步数,等于每个时刻能走的天数之和。
将 nnn 步看成一轮,那么每轮内在一维上走过的一定是个区间。
设 一轮内,走了第 iii 步后,在第 jjj 维走过的这个区间为 [xj+li,j,xj+ri,j][x_j+l_{i,j},x_j+r_{i,j}][xj +li,j ,xj +ri,j ],那么在走到第 i ii 步还没有走出边界的点,就需要满足 1−li,j≤xj≤wj−ri,j1-l_{i,j}\leq x_j\leq w_j-r_{i,j}1−li,j ≤xj ≤wj −ri,j
设 一轮后,第 j jj 维的位移为 djd_jdj 。除了第一轮和最后一轮,走过一轮后,第 jjj 维一定有恰好djd_jdj 个位置走出边界,那么第 2 + t ( t ≥ 0 ) 2+t(t\geq 0)2+t(t≥0) 轮的第 i ii 步时,第 j jj 维能用的位置就有 wj−max(rn,j,ri,j+dj)+min(ln,j,li,j+dj)−∣dj∣×tw_j-\max(r_{n,j},r_{i,j}+d_j)+min(l_{n,j},l_{i,j}+d_j)-|d_j|\times twj −max(rn,j ,ri,j +dj )+min(ln,j ,li,j +dj
)−∣dj ∣×t个
乘起来,就得到了第 t tt 轮,第 i ii 步时还没有走出边界的起点个数。发现这是个关于 t tt 的 k kk 次多项式,记为 fi(t)=∑j=0kajtjf_i(t)=\sum_{j=0}^k a_jt^jfi (t)=∑j=0k aj tj
,不难得出 ttt 的上界,记为tmaxt_{max}tmax
,那么贡献就是∑t=0tmaxfi(t)=∑t=0tmax∑j=0kajtj=∑j=0kaj∑t=0tmaxtj\sum_{t=0}^{t_{max}}f_i(t)=\sum_{t=0}^{t_{max}}\sum_{j=0}^ka_jt^j=\sum_{j=0}^ka_j\sum_{t=0}^{t_{max}}t^j∑t=0tmax fi (t)=∑t=0tmax ∑j=0k aj tj=∑j=0k aj ∑t=0tmax tj
后面是个自然数幂和,用拉格朗日插值搞搞就行。那么每次需要 k2k^2k2暴力卷出fi(t)f_i(t)fi (t),时间复杂度就是O(nk2)O(nk^2)O(nk2)。
以及第 111 轮和第tmax+t_{max}+tmax +轮要单独计算,用那个将每一维可用起点数乘起来的做法算即可。
AC代码