FZ操场（数学，推公式）

题目不复杂，主要是数学的计算，常用公式要熟练

写得比较啰嗦，把整个解题过程都写出来了，步骤都没有省略，认真看，基本都能看懂

题目描述

一个稀疏平常的下午，润德楼 5 楼奥赛机房里的人们正在各自做（划）各自的事（水）：
有的人打开了 majsoul：“自摸 nya，四暗刻，48000点，翻一啦”
有的人打开了 hollow knight：“小老弟，怎么回事？你的前摇怎么这么长？”
有的人打开了 tetris：“Nice！Perfect-clear！”
有的人打开了 hearth stone：“4费7-7，这卡太超模了”
而你却打开了 qq：“…”被 czhou 爆 D 的你只好下来跑步，你发现操场是个由 n 个矩形拼接而成的图形，且每个矩形都过一条“中轴线”。
具体来说，若将操场放在一个平面直角坐标系上，则操场可以由 n 个四元组 (x1i,y1i,x2i,y2i)表示，其中对于 i∈[2,n],y2i−1=y1i ，对于 j∈[1,n],x1i≤−1,x2i≥1。由于你划水太多，czhou 罚你将操场的每对格点跑过去。
具体的说，每次你会选取两个 1×1的正方形 A,B，在操场内沿着曼哈顿最短路从 A 跑到 B（格点是四连通的）。且如果你已经从 A跑到 B，则无需再从 B 跑到 A。
跑完之后，你想知道你今天跑了多长。为了体现 czhou 的良心，只需输出答案对模 998 244 353的结果。

题目简洁表示

n组数据，对于每一组数据，在一个平面直角坐标系上，用四元组$(x1,y1,x2,y2)$来表示一个操场，现求操场中每对格子之间的曼哈顿最短路距离之和，输出答案对模 $998244353$的结果。

输入

• 第一行一个正整数 $n(n<=10^6)$，表示矩形个数。
• 第二到 $n+1$ 行，每行四个整数 $x1,y1,x2,y2(|x1,y1,x2,y2|<=10^9)$，表示从上到下数第 $i$ 个矩形的左边界坐标，上边界坐标，右边界坐标，下边界坐标。

输出

• 一行一个整数，表示距离之和模 $998244353$

样例输入

1 -1 1 1 -1

样例输出

8

提示

其中一共有6对格点 分别为： 黄到绿，距离为1； 黄到紫，距离为1； 黄到红，距离为2； 绿到紫，距离为2； 绿到红，距离为1； 紫到红，距离为1； 所以总距离为1+1+2+2+1+1=8

---

个人题目思路

• 需要用到的公式

  • $$\sum _{i=1}^{n}i=\frac{n(n+1)}{2}$$

  • $$\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$$

  • $$\sum _{i=1}^n{i}^3=[\frac{n(n+1)}{2}{]}^2$$

  • $$\sum _{i=1}^{n}i(i+1)=\frac{n(n+1)(n+2)}{3}$$

坐标给出，只是为了得出矩形的长宽，现设短边为a，长边为b $(a<=b)$

画画图可以发现，假设$a=4,b=6$

123456

2	3	4	5	6	7
3	4	5	6	7	8
4	5	6	7	8	9

从短边对角线的方向看，可以得出，每条对角线上的元素个数

对角线1元素个数: 1
对角线2元素个数: 2
对角线3元素个数: 3
对角线4元素个数: 4
对角线5元素个数: 4
对角线6元素个数: 4
对角线7元素个数: 3
对角线8元素个数: 2
对角线9元素个数: 1

在我们计算答案的时候可以发现:

• 距离为1的点对的个数为$1\ast 2+2\ast 3+3\ast 4+4\ast 4+4\ast 4+4\ast 3+3\ast 2+2\ast 1$

• 距离为2的点对的个数为$1\ast 3+2\ast 4+3\ast 4+4\ast 4+4\ast 3+4\ast 2+3\ast 1$

但是如果这样计算我们会发现，需要线性扫多遍才能得出答案，这样时间复杂度是过不去的

我们又可以发现每次计算时，是有两种对角线方向的，那么对于距离为1的点对单独求，而对于距离大于1的点对可以只用算一遍，然后乘2即可

为了解决时间复杂度的问题，换一种计算思路可以发现：

• 在对角线2中有2个元素，其中存在1种距离为2，即答案为$2\ast 1$

• 在对角线3中有3个元素，其中存在2种距离分别为2，4，即答案为$2\ast 2+4\ast 1$

• 在对角线4中有4个元素，其中存在3种距离分别为2，4，6，即答案为$2\ast 3+4\ast 2+6\ast 1$

• 类推下去可得：

• 对于某条对角线，其中有n个元素，即答案贡献为${\sum }_{i=1}^{n-1}2i(n-i)$

• 这里是没有统计距离为1的点对的贡献，因此需要单独统计距离为1的点对的贡献

  • $1\ast 2+2\ast 3+3\ast 4+4\ast 4+4\ast 4+4\ast 3+3\ast 2+2\ast 1$

• 因此最终答案为$\sum （一个方向所有对角线的贡献）\ast 2+距离为1的点对的贡献$

通过观察可以发现，对于矩形$a\times b$，短边对角线元素个数为:
$$1,2,3,4,\cdot \cdot \cdot ,a,a,\cdot \cdot \cdot ,a,\cdot \cdot \cdot ,4,3,2,1$$ 其中含有$(b-a+1)$个$a$

因此所有对角线的贡献为：

$$tmp1=2\ast [2\sum _{x=2}^{a-1}\sum _{i-1}^{x-1}2i(x-i)+(b-a+1)\sum _{i=1}^{a-1}2i(a-i)]$$

距离为1的点对的贡献为：

$1\ast 2+2\ast 3+\cdot \cdot \cdot +(a-1)\ast a+a\ast a+\cdot \cdot \cdot +a\ast a+a\ast (a-1)+\cdot \cdot \cdot +3\ast 2+2\ast 1$
$$=2\sum _{i=1}^{a-1}i(i+1)+(b-a)\ast a^2=tmp2$$

因此最终答案为：$ans=tmp1+tmp2$

$$=2\ast [2\sum _{x=2}^{a-1}\sum _{i-1}^{x-1}2i(x-i)+(b-a+1)\sum _{i=1}^{a-1}2i(a-i)]+2\sum _{i=1}^{a-1}i(i+1)+(b-a)\ast a^2$$

---

用我们准备的公式来化简这看似复杂的式子：

$$tmp1=2\ast [2\sum _{x=2}^{a-1}(2x\sum _{i=1}^{x-1}i-2\sum _{i=1}^{x-1}{i}^2)+(b-a+1)(2a\sum _{i=1}^{a-1}i-2\sum _{i=1}^{a-1}{i}^2)]$$

$$=2\ast \{2\sum _{x=2}^{a-1}[x\ast x(x-1)-\frac{(x-1)x(2x-1)}{3}]+(b-a+1)[a\ast a(a-1)-\frac{(a-1)a(2a-1)}{3}]\}$$

$$=2\ast [\frac{2}{3}\sum _{x=2}^{a-1}(x^3-x)+(b-a+1)(\frac{a^3}{3}-\frac{a}{3})]$$

$$=2\ast \{\frac{2}{3}[\sum _{x=1}^{a-1}(x^3-x)-(1-1)]+(b-a+1)(\frac{a^3}{3}-\frac{a}{3})\}$$

$$=2\ast [\frac{2}{3}(\sum _{x=1}^{a-1}{x}^3-\sum _{x=1}^{a-1}x)+(b-a+1)(\frac{a^3}{3}-\frac{a}{3})]$$

$$=2\ast \{\frac{2}{3}[\frac{(a-1)a}{2}{]}^2-\frac{a(a-1)}{3}+(b-a+1)(\frac{a^3}{3}-\frac{a}{3})\}$$

---

$$tmp2=2\sum _{i=1}^{a-1}i(i+1)+(b-a)\ast a^2$$

$$=2\frac{(a-1)a(a+1)}{3}+b{a}^2-a^3$$

$$=b{a}^2-\frac{a^3}{3}-\frac{2}{3}a$$

---

那么tmp1和tmp2都可以$O(1)$计算出来了，由于有分母，那么预处理一下2和3的逆元就行了

#pragma GCC optimize(3, "Ofast", "inline") #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<vector> #include<ctime>using namespace std;typedef long long LL;typedef unsigned long long uLL;#define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i) #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i) #define EREP(i, a) for(register int i = (be[a]); i != -1; i = nxt[i]) #define debug(...) fprintf(stderr, __VA_ARGS__) #define mem(a, b) memset((a), b, sizeof(a))template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }template <class T> T read(T sum = 0, T fg = 0) {char c = getchar();while(c < '0' || c > '9') { fg |= c == '-'; c = getchar(); }while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); }return fg ? -sum : sum; }const int inf = 1e9;const LL INF = 1e17;const int Size = 3e5 + 5;const LL mod = 998244353;LL qpow(LL a, LL N) {LL ans = 1LL;while(N){if(N & 1LL) ans = ans * a % mod;a = a * a % mod;N >>= 1LL;}return ans % mod; }LL inv3, inv2;void solve() {LL x1 = read<LL>(), y1 = read<LL>(), x2 = read<LL>(), y2 = read<LL>();LL a = x2 - x1, b = y2 - y1;if(a < 0) a = -a;if(b < 0) b = -b;if(a > b) swap(a, b);LL ans = ((qpow(a, 3) * inv3 % mod - a * inv3 % mod) % mod + mod) % mod;ans = ans * (b - a + 1) % mod;LL tmp = qpow((a - 1) * a % mod * inv2 % mod, 2) * 2LL % mod * inv3 % mod;tmp = (((tmp - a * (a - 1) % mod * inv3 % mod) % mod) + mod) % mod;ans = (ans + tmp) * 2LL % mod;ans = (ans + (a - 1) * a % mod * (a + 1) % mod * inv3 % mod * 2LL % mod) % mod;ans = (ans + (b - a) * qpow(a, 2) % mod) % mod;printf("%lld\n", (tmp + ans) % mod); }int main() { #ifndef ONLINE_JUDGEfreopen("input.in", "r", stdin);freopen("output.out", "w", stdout); #endifinv2 = qpow(2, mod - 2);inv3 = qpow(3, mod - 2);int n = read<int>();while(n--) solve();return 0; }

第一次写这么复杂的数学题，代码简单，主要还是推式子

总结

以上是生活随笔为你收集整理的FZ操场（数学，推公式）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。