Warning: session_start(): open(/tmp/sess_c89df4a4c59409e2428dd7852a2d1012, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/6/6a0f3843c5ea426c08feea4e44f84973.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
比赛链接：[[https://atcoder.jp/contests/abc127|AtCoder Beginner Contest 127]]
==== E - Cell Distance ====
=== 题意 ===
给一个 $n\times m$ 的网格和一个整数 $k$ ，每次取 $k$ 个格子 $(x_i,y_i)$ 得到 $v = \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(|x_i-x_j|+|y_i-y_j|)$。求所有不同取法的 $\sum v$ 。
=== 数据范围 ===
$2 \le n\times m \le 2\times 10^5$
$2 \le k \le n\times m$
=== 题解 ===
考虑两个格子 $(x_i,y_i)$ 和 $(x_j,y_j)$ 对答案的贡献为 $(|x_i-x_j|+|y_i-y_j|){k-2 \choose nm-2}$，所以只要求一遍两两 $|x_i-x_j|+|y_i-y_j|$ 的值即可。
#include
#define ll long long
#define pii_ pair
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<
\\