企业官网建设流程全解析

## 题目大意

给定 $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)$，$N=1500$ 时约 $5\times 10^{12}$，超时。

---

## 二、核心转化

切比雪夫距离有恒等式：

$$
\max(|x|,|y|) = \frac{|x+y|+|x-y|}{2}
$$

令 $u=i+j$，$v=i-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)$ 只依赖 $u=i+j$
- $Q(v)$ 只依赖 $v=i-j$

所以预处理所有 $P(u)$、$Q(v)$，每个格子 $O(1)$ 查询。

---

## 四、计算 $P(u)$

按主对角线分组：$S_u(t)=\sum_{i'+j'=t}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)$ 同理，按副对角线分组，$v=i-j$ 加 $N$ 偏移。

---

## 五、算法流程

1. 读入数据，计算 $w(i,j)=(A_i\times B_j)\bmod M$
2. 累加 `su[i+j] += w`，`sv[i-j+n] += w`
3. 对 `su`、`sv` 做前缀和
4. 对每个 $u$ 算 $P(u)$，每个 $v$ 算 $Q(v)$
5. 遍历格子：$f=(P[i+j]+Q[i-j+n])/2$，累加异或

复杂度 $O(N^2)$。

---

## 六、参考代码

```cpp
#include<bits/stdc++.h>
#define int long long
using 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(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int w=(a[i]*b[j])%m;
u[i+j]+=w;
v[i-j+n]+=w;
}
}
int U=2*n;
for(int i=1;i<=U;i++){
p[i]=p[i-1]+u[i];
q[i]=q[i-1]+u[i]*i;
}
for(int i=2;i<=U;i++){
P[i]=i*p[i]-q[i]+(q[U]-q[i])-i*(p[U]-p[i]);
}
int V=2*n-1;
for(int i=1;i<=V;i++){
r[i]=r[i-1]+v[i];
s[i]=s[i-1]+v[i]*i;
}
for(int i=1;i<=V;i++){
Q[i]=i*r[i]-s[i]+(s[V]-s[i])-i*(r[V]-r[i]);
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int f=(P[i+j]+Q[i-j+n])/2;
ans^=f+(i-1)*n+(j-1);
}
}
cout<<ans<<endl;
return 0;
}
```

---

## 七、易错点

1. $P+Q$ 是两倍距离和，最后要除以 $2$
2. $i-j$ 可能为负，加 $N$ 偏移
3. 异或项是 $f+(i-1)N+(j-1)$，注意减 $1$
4. 权重和可能很大，用 `long long`
5. $A_i\times B_j$ 取模前可能溢出，用 `long long` 计算