## 题目大意给定 $N \times N$ 的网格格子 $(i,j)$ 的人数 $w(i,j) (A_i \times B_j) \bmod M$。对每个格子 $(i,j)$求所有人到它的**切比雪夫距离**费用总和 $f(i,j)$其中距离定义为$$d \max(|s_r-t_r|, |s_c-t_c|)$$最后求所有 $f(i,j)(i-1)N(j-1)$ 的异或和。数据范围$N \le 1500$$M \le 2\times 10^6$。---## 一、暴力不可行枚举每个目标格子 $(i,j)$再枚举所有格子累加距离复杂度 $O(N^4)$$N1500$ 时约 $5\times 10^{12}$超时。---## 二、核心转化切比雪夫距离有恒等式$$\max(|x|,|y|) \frac{|xy||x-y|}{2}$$令 $uij$$vi-j$则$$\max(|i-i|,|j-j|) \frac{|u-u||v-v|}{2}$$二维切比雪夫距离被拆成两个**一维曼哈顿距离**。---## 三、拆分 $f(i,j)$$$f(i,j) \frac{1}{2}\left(\underbrace{\sum w(i,j)|u-u|}_{P(u)} \underbrace{\sum w(i,j)|v-v|}_{Q(v)}\right)$$- $P(u)$ 只依赖 $uij$- $Q(v)$ 只依赖 $vi-j$所以预处理所有 $P(u)$、$Q(v)$每个格子 $O(1)$ 查询。---## 四、计算 $P(u)$按主对角线分组$S_u(t)\sum_{ijt}w(i,j)$。则 $P(u)\sum_t S_u(t)|u-t|$。拆成左右两部分用前缀和- $pu[x]\sum_{t\le x}S_u(t)$- $qu[x]\sum_{t\le x}t\cdot S_u(t)$则$$P(u) u\cdot pu[u]-qu[u] (qu[U]-qu[u]) - u\cdot(pu[U]-pu[u])$$$Q(v)$ 同理按副对角线分组$vi-j$ 加 $N$ 偏移。---## 五、算法流程1. 读入数据计算 $w(i,j)(A_i\times B_j)\bmod M$2. 累加 su[ij] wsv[i-jn] w3. 对 su、sv 做前缀和4. 对每个 $u$ 算 $P(u)$每个 $v$ 算 $Q(v)$5. 遍历格子$f(P[ij]Q[i-jn])/2$累加异或复杂度 $O(N^2)$。---## 六、参考代码cpp#includebits/stdc.h#define int long longusing namespace std;int n,m;int a[1505],b[1505];int u[3005],v[3005];int p[3005],q[3005];int r[3005],s[3005];int P[3005],Q[3005];signed main(){cinnm;for(int i1;in;i)cina[i];for(int i1;in;i)cinb[i];for(int i1;in;i){for(int j1;jn;j){int w(a[i]*b[j])%m;u[ij]w;v[i-jn]w;}}int U2*n;for(int i1;iU;i){p[i]p[i-1]u[i];q[i]q[i-1]u[i]*i;}for(int i2;iU;i){P[i]i*p[i]-q[i](q[U]-q[i])-i*(p[U]-p[i]);}int V2*n-1;for(int i1;iV;i){r[i]r[i-1]v[i];s[i]s[i-1]v[i]*i;}for(int i1;iV;i){Q[i]i*r[i]-s[i](s[V]-s[i])-i*(r[V]-r[i]);}int ans0;for(int i1;in;i){for(int j1;jn;j){int f(P[ij]Q[i-jn])/2;ans^f(i-1)*n(j-1);}}coutansendl;return 0;}---## 七、易错点1. $PQ$ 是两倍距离和最后要除以 $2$2. $i-j$ 可能为负加 $N$ 偏移3. 异或项是 $f(i-1)N(j-1)$注意减 $1$4. 权重和可能很大用 long long5. $A_i\times B_j$ 取模前可能溢出用 long long 计算