出生点

GitHub 跳转原题关系图返回列表

先算完整 n×m 网格所有出生点对的曼哈顿距离和，再减去所有涉及障碍点的贡献，最后补回障碍之间被多减的一次。

OJ: luogu

题目 ID: P6692

难度:提高+/省选-

标签:数学推导曼哈顿距离组合计数思维

日期: 2026-06-20 07:09

题意

在一个 n x m 的网格里，有 k 个障碍点不能出生。

小 W 和小 H 会各自随机出生在一个非障碍点上。
如果两人交换出生点，视为同一种情况；两人也可以出生在同一个点上。

要求输出：

所有合法出生点安排中，两人曼哈顿距离的总和

思路

先看一个可以直接验证的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    set<pair<int, int>> blocked;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        blocked.insert({x, y});
    }

    vector<pair<int, int>> pts;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!blocked.count({i, j})) {
                pts.push_back({i, j});
            }
        }
    }

    i64 ans = 0;
    for (int i = 0; i < (int) pts.size(); i++) {
        for (int j = i; j < (int) pts.size(); j++) {
            ans += llabs(pts[i].first - pts[j].first)
                 + llabs(pts[i].second - pts[j].second);
        }
    }

    cout << ans << '\n';
    return 0;
}

暴力版先把所有非障碍点列出来，再枚举所有 i <= j 的点对，直接累加曼哈顿距离。

正解的关键是：

先算完整网格的答案
再把障碍点带来的影响修正掉

1. 完整网格的答案

如果没有障碍，那么曼哈顿距离可以拆成横纵两个方向分别统计。

先看行坐标部分。
假设两点的行分别是 i < j，那么它们在行方向贡献：

j - i

而列可以随便选，有 m^2 种搭配。
所以行方向总贡献是：

m^2 * sum_{1<=i<j<=n} (j-i)

同理，列方向总贡献是：

n^2 * sum_{1<=i<j<=m} (j-i)

并且有经典公式：

sum_{1<=i<j<=L} (j-i) = L(L-1)(L+1)/6

于是完整网格总答案可以直接算出来。

2. 删除障碍点

设完整网格点集是 U，障碍点集合是 B，真正可出生点集合是 R = U - B。

我们想要的是：

sum_{p,q in R, p<=q} dist(p,q)

可以从完整答案里扣掉所有“涉及障碍点”的点对。

对一个障碍点 (x, y) 来说，它到整张网格所有点的距离和是：

m * sum_{i=1}^n |x-i| + n * sum_{j=1}^m |y-j|

其中：

sum_{i=1}^n |x-i|

可以拆成左边一段和右边一段，直接公式算。

把所有障碍点都这样减掉后，会有一个重复：

障碍点之间的点对被减了两次

所以最后还要把“障碍点之间的曼哈顿距离和”补回一次。

3. 最终公式

于是最终答案就是：

完整网格总和
减去所有障碍点到整张网格的距离和
加上障碍点之间的无序距离和

障碍点之间的距离和也能拆成 x 和 y 两部分，排序后用前缀和在线性里算完。

4. 为什么要手写大整数

n, m 都能到 1e9，答案量级远远超过 long long。
这题没有取模，所以必须输出完整整数。

本地编译环境没有 boost::multiprecision，所以代码里手写了一个只支持：

加法
减法
乘小整数
除小整数

的非负大整数，已经够用。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

struct BigInt {
    static const int BASE = 1000000000;
    vector<int> d; // 小端存储

    BigInt(i64 x = 0) {
        if (x == 0) {
            d.push_back(0);
            return;
        }
        while (x > 0) {
            d.push_back((int) (x % BASE));
            x /= BASE;
        }
    }

    void trim() {
        while (d.size() > 1 && d.back() == 0) {
            d.pop_back();
        }
    }

    BigInt &operator += (const BigInt &other) {
        int n = max(d.size(), other.d.size());
        d.resize(n, 0);

        i64 carry = 0;
        for (int i = 0; i < n; i++) {
            i64 cur = carry + d[i];
            if (i < (int) other.d.size()) {
                cur += other.d[i];
            }
            d[i] = (int) (cur % BASE);
            carry = cur / BASE;
        }

        if (carry) {
            d.push_back((int) carry);
        }
        return *this;
    }

    BigInt &operator -= (const BigInt &other) {
        i64 borrow = 0;
        for (int i = 0; i < (int) d.size(); i++) {
            i64 cur = (i64) d[i] - borrow;
            if (i < (int) other.d.size()) {
                cur -= other.d[i];
            }

            if (cur < 0) {
                cur += BASE;
                borrow = 1;
            }
            else {
                borrow = 0;
            }
            d[i] = (int) cur;
        }

        trim();
        return *this;
    }

    BigInt mul_small(i64 x) const {
        if (x == 0) {
            return BigInt(0);
        }

        BigInt res;
        res.d.assign(d.size(), 0);

        i64 carry = 0;
        for (int i = 0; i < (int) d.size(); i++) {
            i64 cur = (i64) d[i] * x + carry;
            res.d[i] = (int) (cur % BASE);
            carry = cur / BASE;
        }

        while (carry > 0) {
            res.d.push_back((int) (carry % BASE));
            carry /= BASE;
        }
        res.trim();
        return res;
    }

    BigInt div_small(int x) const {
        BigInt res;
        res.d.assign(d.size(), 0);

        i64 rem = 0;
        for (int i = (int) d.size() - 1; i >= 0; i--) {
            i64 cur = rem * BASE + d[i];
            res.d[i] = (int) (cur / x);
            rem = cur % x;
        }

        res.trim();
        return res;
    }

    string to_string() const {
        string s = std::to_string(d.back());
        char buf[16];
        for (int i = (int) d.size() - 2; i >= 0; i--) {
            snprintf(buf, sizeof(buf), "%09d", d[i]);
            s += buf;
        }
        return s;
    }
};

BigInt operator + (BigInt a, const BigInt &b) {
    a += b;
    return a;
}

BigInt operator - (BigInt a, const BigInt &b) {
    a -= b;
    return a;
}

int k;
i64 n, m;
vector<i64> xs, ys;

// 计算 pos 到 1..len 所有点的距离和。
BigInt sum_to_all(i64 len, i64 pos) {
    BigInt left = BigInt(pos - 1).mul_small(pos).div_small(2);
    i64 right_cnt = len - pos;
    BigInt right = BigInt(right_cnt).mul_small(right_cnt + 1).div_small(2);
    return left + right;
}

// 计算一个有序数组中，两两差值和。
BigInt pair_diff_sum(vector<i64> a) {
    sort(a.begin(), a.end());

    BigInt ans(0);
    BigInt prefix(0);
    for (int i = 0; i < (int) a.size(); i++) {
        BigInt cur((i64) a[i] * i);
        cur -= prefix;
        ans += cur;
        prefix += BigInt(a[i]);
    }
    return ans;
}

BigInt line_pair_sum(i64 len) {
    // sum_{1<=i<j<=len} (j-i) = len*(len-1)*(len+1)/6
    BigInt res(len);
    res = res.mul_small(len - 1);
    res = res.mul_small(len + 1);
    res = res.div_small(6);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    xs.resize(k);
    ys.resize(k);
    for (int i = 0; i < k; i++) {
        cin >> xs[i] >> ys[i];
    }

    // 完整 n*m 网格中，所有无序点对的曼哈顿距离总和。
    BigInt total_full = line_pair_sum(n).mul_small(m).mul_small(m)
                      + line_pair_sum(m).mul_small(n).mul_small(n);

    // 障碍点到整张网格所有点的距离和（每个障碍点只算一次）。
    BigInt remove_sum(0);
    for (int i = 0; i < k; i++) {
        remove_sum += sum_to_all(n, xs[i]).mul_small(m);
        remove_sum += sum_to_all(m, ys[i]).mul_small(n);
    }

    // 障碍点之间的无序距离和。前面 remove_sum 把这些对减了两次，这里补回一次。
    BigInt blocked_pair_sum = pair_diff_sum(xs) + pair_diff_sum(ys);

    BigInt answer = total_full + blocked_pair_sum;
    answer -= remove_sum;
    cout << answer.to_string() << '\n';
    return 0;
}

复杂度

设障碍数为 k。

读入并统计障碍对整图贡献： $O(k)$
排序并计算障碍点之间距离和： $O(k log k)$

总时间复杂度：

$O(k log k)$

空间复杂度：

$O(k)$

总结

这题最核心的想法不是“直接数可出生点”，而是：

先算完整网格答案
再按障碍做删点修正

因为障碍只有 5e5 个，而整张图可能有 1e18 个点，所以必须把复杂度压到只和障碍数有关。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P6692 出生点

题目背景

小 L、小 W 和小 H 在一起van♂游戏。

~~由于小 L 太菜了所以导致他一直在看着小 W 和小 H 打游戏。~~

题目描述

这款游戏的地图可以抽象成一张有 $n$ 行 $m$ 列的网格图，网格图上有 $k$ 个障碍点，相邻两点间边长为 $1$ 。游戏开始时~~小 L~~、小 W 和小 H 会各自随机出生在一个点。当然，他们不会出生在障碍点。

~~经常开局死的~~小 L 看着小 W 和小 H 每次在地图上汇合时经过的路径，很想知道他们每次出生后两个人之间的期望距离。（这里的距离指两点间曼哈顿距离，即 $\left|x_1-x_2\right|+\left|y_1-y_2\right|$ ）

由于小 L 可以非常容易算出有多少种出生点安排方案，所以你实际上只需要告诉他所有情况中他们两人距离之和。

注意：小 W 出生在点 $A$ ，小 H 出生在点 $B$ ，跟小 W 出生在点 $B$ ，小 H 出生在点 $A$ ，这两种情况视作同一种情况。

输入格式

第一行有三个整数 $n,m,k$ ，分别表示地图行数、列数以及障碍物点数。

接下来有 $k$ 行，第 $i$ 行有两个正整数 $x_i,y_i$ ，表示第 $i$ 个障碍物的位置。

输出格式

一个整数，表示所有情况中小 W 和小 H 两人出生点距离之和。

由于小 L 十分无聊，所以他让你将答案对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

对于样例一，地图样式如下（其中蓝点为障碍点，红点为可能的出生点）：

出生点为 $(1,1)$ 和 $(1,1)$ ，距离为 $0$ 。
出生点为 $(1,1)$ 和 $(1,2)$ ，距离为 $1$ 。
出生点为 $(1,1)$ 和 $(1,3)$ ，距离为 $2$ 。
出生点为 $(1,1)$ 和 $(2,2)$ ，距离为 $2$ 。
出生点为 $(1,1)$ 和 $(2,3)$ ，距离为 $3$ 。
出生点为 $(1,1)$ 和 $(3,1)$ ，距离为 $2$ 。
出生点为 $(1,1)$ 和 $(3,2)$ ，距离为 $3$ 。
出生点为 $(1,2)$ 和 $(1,2)$ ，距离为 $0$ 。
出生点为 $(1,2)$ 和 $(1,3)$ ，距离为 $1$ 。
出生点为 $(1,2)$ 和 $(2,2)$ ，距离为 $1$ 。
出生点为 $(1,2)$ 和 $(2,3)$ ，距离为 $2$ 。
出生点为 $(1,2)$ 和 $(3,1)$ ，距离为 $3$ 。
出生点为 $(1,2)$ 和 $(3,2)$ ，距离为 $2$ 。
出生点为 $(1,3)$ 和 $(1,3)$ ，距离为 $0$ 。
出生点为 $(1,3)$ 和 $(2,2)$ ，距离为 $2$ 。
出生点为 $(1,3)$ 和 $(2,3)$ ，距离为 $1$ 。
出生点为 $(1,3)$ 和 $(3,1)$ ，距离为 $4$ 。
出生点为 $(1,3)$ 和 $(3,2)$ ，距离为 $3$ 。
出生点为 $(2,2)$ 和 $(2,2)$ ，距离为 $0$ 。
出生点为 $(2,2)$ 和 $(2,3)$ ，距离为 $1$ 。
出生点为 $(2,2)$ 和 $(3,1)$ ，距离为 $2$ 。
出生点为 $(2,2)$ 和 $(3,2)$ ，距离为 $1$ 。
出生点为 $(2,3)$ 和 $(2,3)$ ，距离为 $0$ 。
出生点为 $(2,3)$ 和 $(3,1)$ ，距离为 $3$ 。
出生点为 $(2,3)$ 和 $(3,2)$ ，距离为 $2$ 。
出生点为 $(3,1)$ 和 $(3,1)$ ，距离为 $0$ 。
出生点为 $(3,1)$ 和 $(3,2)$ ，距离为 $1$ 。
出生点为 $(3,2)$ 和 $(3,2)$ ，距离为 $0$ 。

总和为 $42$ 。

数据范围

本题采用捆绑测试。

Subtask 1( $10\%$ )： $n,m\leq 80$ 。
Subtask 2( $20\%$ )： $n,m\leq 5000$ 。
Subtask 3( $15\%$ )： $k=0$ 。
Subtask 4( $15\%$ )： $m=1$ 。
Subtask 5( $40\%$ )：无特殊限制。

对于 $100\%$ 的数据， $1\leq n,m\leq 10^9,1\leq x_i\leq n,1\leq y_i\leq m,0\leq k\leq 5\times 10^5,k<n\times m$ ，保证所有障碍点各不相同。

出生点

目录

题意

思路

1. 完整网格的答案

2. 删除障碍点

3. 最终公式

4. 为什么要手写大整数

代码

复杂度

总结

一图流解析