题面\(O(nd^2)\)考虑\(f(i,j,k)\)表示dp到第\(i\)维，距离\(p,q\)曼哈顿距离\(j,k\)的方案数。考虑朴素转移：设\(dis=|p_{i+1}-q_{i+1}|\)。\[\begin{aligned}f(i+1,j+t,k+dis-t)&\getsf(i,j,k)&(0\leqt\leqdis)\quad&(1)\\f(i+1,j+d+t,k+t)&\ge