Atcoder ABC 127E（数学，计数，概率）

题目链接

https://atcoder.jp/contests/abc127/tasks/abc127_e

题意

给定一个矩阵，包含 $N \times M$ 个格子，现在从中选出 $K \leq N \times M$ 个不同的格子，记为 $(x_{1}, y_{1}), (x_{2}, y_{2}), \dots, (x_{K}, y_{K})$ ，记

$c o s t = \sum_{i = 1}^{K - 1} \sum_{j = i + 1}^{K} (| x_{i} - x_{j} | + | y_{i} - y_{j} |)$

求：对于所有不同的 $K$ 个格子的选法， $c o s t$ 的sum为多少？

法一概率

选 $k$ 个格子的方案数为 $C (n + m, k)$ ，在 $k$ 个格子中，任选 $2$ 个出来，有 $C (k, 2)$ 种，考虑它们的贡献：

因为是全部方案，所以可以考虑用 期望值 来做！

问题转化为，从 $N \times M$ 的矩阵中，选择 $2$ 个不同的点 $(x_{i}, y_{i}), (x_{j}, y_{j})$ ，求 $| x_{i} - x_{j} | + | y_{i} - y_{j} |$ 的期望？

期望为： $\frac{n + m}{3}$

如果推式子很难，这里是一些小技巧（仅用于分母中无 $n, m$ ，并且分子中不存在 $n m$ 之类的项）：

打表找规律：假设期望值 $E (n, m)$ 是一个关于 $n, m$ 的多项式，那么固定一下 $n$ 的值，然后让 $m = 1, 2, 3 \dots$ 来打表找出 $E (n, m)$ 和 $m$ 的关系。同理可以找出 $E (n, m)$ 和 $n$ 的关系，相加一下就可以了。

拉格朗日插值法：设 $a n s = F (n, m) = E (n, m) * C (n m, 2)$ ，我们可以固定 $n$ ，然后用插值法找出 $F (n, m)$ 和 $m$ 的关系。（这个函数有两个变量，按理说应该是固定每一个 $n$ 然后对每一个 $n$ 都进行一次插值法的，以后遇到了可以尝试一下。）

严谨证明：

考虑一个点 $(x, y)$ ，那么

纵向贡献 为： $v_{x, y} = [(1 + 2 + \dots + x - 1) + (1 + 2 + \dots + n - x)] * m$

横向贡献 为： $h_{x, y} = [(1 + 2 + \dots y - 1) + (1 + 2 + \dots + m - y)] * n$

期望就是 $E (n, m) = \frac{\sum_{x = 1}^{n} \sum_{y = 1}^{m} (v_{x, y} + h_{x, y})}{C (n m, 2)} = \frac{n + m}{3}$

以上，最终的答案就是

$a n s = C (n m, k) * C (k, 2) * \frac{n + m}{3}$

法二计数

我们选择 $2$ 个格子，有 $C (n m - 2, k - 2)$ 种。

对于横坐标的差值为 $d_{x}$ 的情况，有 $(n - d_{x}) m^{2}$ 种。贡献就是 $(n - d_{x}) m^{2} * d_{x}$

对于纵坐标的差值为 $d_{y}$ 的情况，有 $(m - d_{y}) n^{2}$ 种。贡献就是 $(m - d_{y}) n^{2} * d_{y}$

所以答案就是

$a n s = C (n m - 2, k - 2) (\sum_{d_{x} = 1}^{n - 1} (n - d_{x}) m^{2} * d_{x} + \sum_{d_{y} = 1}^{m - 1} (m - d_{y}) n^{2} * d_{y})$

代码

copy
using namespace std;
#include <bits/stdc++.h>
#define ll long long
const int mod = 1e9+7;
const int maxn = 2e5+5;
ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1)
            (res *= a) %= mod;
        (a *= a) %= mod;
        b >>= 1;
    }
    return res;
}
ll inv(ll a) {
    return qpow(a, mod-2);
}
ll n,m,k;
ll fac[maxn];
void init() {
    fac[0] = 1;
    fac[1] = 1;
    for (int i = 2; i <= n*m; i++) {
        fac[i] = (fac[i-1] * (ll)(i)) % mod;
    }
}
int main() {
    cin >> n >> m >> k;
    init();
    ll nu = fac[n*m] * k % mod * (k-1) % mod * (n+m) % mod;
    ll de = inv(fac[k]) * inv(fac[n*m-k]) % mod * inv(6) % mod;
    cout << (nu * de) % mod << endl;
}

参考链接

一些数学知识

Q1. 如果不限定坐标为整数，长度为 $n$ 的线段上任取两个点，距离期望值是？

A1. 答案为 $\frac{n}{3}$ ，有两种方法。

第一种：先假设坐标只能为 $1, 2, \dots, n$ 的整数，那么求出的期望是 $E_{n} = 2 \times \frac{\sum_{i = 1}^{n} i (n - i)}{n^{2}} = \frac{n^{2} - 1}{3 n}$ ，取一个 $n$ 趋向无穷，就有 $E = lim_{n \to \infty} \frac{n^{2} - 1}{3 n} = \frac{n}{3}$

上述推导需要用到 $1^{2} + 2^{2} + \dots + n^{2} = \frac{1}{6} n (n + 1) (2 n + 1)$

第二种：先假设线段长度为 $1$ ，则有期望为 $\frac{\int_{0}^{1} \int_{0}^{1} | x - y | d y d x}{\int_{0}^{1} \int_{0}^{1} 1 d y d x} = \int_{0}^{1} \int_{0}^{x} (x - y) d y d x + \int_{0}^{1} \int_{x}^{1} (y - x) d y d x = \frac{1}{3}$ ，对于线段长度为 $n$ ，乘上 $n$ 即可。（记得分母要除以样本空间，即 $\int_{0}^{1} \int_{0}^{1} 1 d y d x$ ）

Q2. 如果不限定坐标为整数， $n \times n$ 的正方形中任取两个点，距离期望值是？

A2. 答案约为 $0.521$ ，具体分析可以见这里和这里

其他例题(TODO)

https://www.luogu.com.cn/problem/P4781