欢迎访问 如意编程网!

如意编程网

当前位置: 首页 > 编程资源 > 编程问答 >内容正文

编程问答

FZ操场(数学,推公式)

发布时间:2024/5/15 编程问答 14 豆豆
如意编程网 收集整理的这篇文章主要介绍了 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组数据,对于每一组数据,在一个平面直角坐标系上,用四元组 ( x 1 , y 1 , x 2 , y 2 ) (x1, y1, x2, y2) (x1,y1,x2,y2)来表示一个操场,现求操场中每对格子之间的曼哈顿最短路距离之和,输出答案对模 998244353 998244353 998244353的结果。

输入

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

输出

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

样例输入

1 -1 1 1 -1

样例输出

8

提示

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

个人题目思路

  • 需要用到的公式
    • ∑ i = 1 n i = n ( n + 1 ) 2 \sum^{n}_{i = 1}{i} = \frac{n(n+1)}{2} i=1ni=2n(n+1)

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

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

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

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

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

123456
234567
345678
456789

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

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

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

  • 距离为1的点对的个数为 1 ∗ 2 + 2 ∗ 3 + 3 ∗ 4 + 4 ∗ 4 + 4 ∗ 4 + 4 ∗ 3 + 3 ∗ 2 + 2 ∗ 1 1*2+2*3+3*4+4*4+4*4+4*3+3*2+2*1 12+23+34+44+44+43+32+21

  • 距离为2的点对的个数为 1 ∗ 3 + 2 ∗ 4 + 3 ∗ 4 + 4 ∗ 4 + 4 ∗ 3 + 4 ∗ 2 + 3 ∗ 1 1*3+2*4+3*4+4*4+4*3+4*2+3*1 13+24+34+44+43+42+31

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

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

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

  • 在对角线2中有2个元素,其中存在1种距离为2,即答案为 2 ∗ 1 2 * 1 21

  • 在对角线3中有3个元素,其中存在2种距离分别为2,4,即答案为 2 ∗ 2 + 4 ∗ 1 2 * 2 + 4 * 1 22+41

  • 在对角线4中有4个元素,其中存在3种距离分别为2,4,6,即答案为 2 ∗ 3 + 4 ∗ 2 + 6 ∗ 1 2 * 3 + 4 * 2 + 6 * 1 23+42+61

  • 类推下去可得:

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

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

    • 1 ∗ 2 + 2 ∗ 3 + 3 ∗ 4 + 4 ∗ 4 + 4 ∗ 4 + 4 ∗ 3 + 3 ∗ 2 + 2 ∗ 1 1*2+2*3+3*4+4*4+4*4+4*3+3*2+2*1 12+23+34+44+44+43+32+21
  • 因此最终答案为 ∑ ( 一 个 方 向 所 有 对 角 线 的 贡 献 ) ∗ 2 + 距 离 为 1 的 点 对 的 贡 献 \sum {(一个方向所有对角线的贡献)} * 2 + 距离为1的点对的贡献 线2+1

通过观察可以发现,对于矩形 a × b a×b a×b,短边对角线元素个数为:
1 , 2 , 3 , 4 , ⋅ ⋅ ⋅ , a , a , ⋅ ⋅ ⋅ , a , ⋅ ⋅ ⋅ , 4 , 3 , 2 , 1 1,2,3,4,···,a,a,···,a,···,4,3,2,1 1,2,3,4,,a,a,,a,,4,3,2,1 其中含有 ( b − a + 1 ) (b-a+1) (ba+1) a a a

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

t m p 1 = 2 ∗ [ 2 ∑ x = 2 a − 1 ∑ i − 1 x − 1 2 i ( x − i ) + ( b − a + 1 ) ∑ i = 1 a − 1 2 i ( a − i ) ] tmp1 = 2*[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)}] tmp1=2[2x=2a1i1x12i(xi)+(ba+1)i=1a12i(ai)]

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

1 ∗ 2 + 2 ∗ 3 + ⋅ ⋅ ⋅ + ( a − 1 ) ∗ a + a ∗ a + ⋅ ⋅ ⋅ + a ∗ a + a ∗ ( a − 1 ) + ⋅ ⋅ ⋅ + 3 ∗ 2 + 2 ∗ 1 1*2+2*3+···+(a-1)*a+a*a+···+a*a+a*(a-1)+···+3*2+2*1 12+23++(a1)a+aa++aa+a(a1)++32+21
= 2 ∑ i = 1 a − 1 i ( i + 1 ) + ( b − a ) ∗ a 2 = t m p 2 =2\sum_{i = 1}^{a - 1}{i(i+1)}+(b-a)*a^2=tmp2 =2i=1a1i(i+1)+(ba)a2=tmp2

因此最终答案为: a n s = t m p 1 + t m p 2 ans = tmp1 + tmp2 ans=tmp1+tmp2

= 2 ∗ [ 2 ∑ x = 2 a − 1 ∑ i − 1 x − 1 2 i ( x − i ) + ( b − a + 1 ) ∑ i = 1 a − 1 2 i ( a − i ) ] + 2 ∑ i = 1 a − 1 i ( i + 1 ) + ( b − a ) ∗ a 2 = 2*[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)*a^2 =2[2x=2a1i1x12i(xi)+(ba+1)i=1a12i(ai)]+2i=1a1i(i+1)+(ba)a2


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

t m p 1 = 2 ∗ [ 2 ∑ x = 2 a − 1 ( 2 x ∑ i = 1 x − 1 i − 2 ∑ i = 1 x − 1 i 2 ) + ( b − a + 1 ) ( 2 a ∑ i = 1 a − 1 i − 2 ∑ i = 1 a − 1 i 2 ) ] tmp1 = 2*[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})] tmp1=2[2x=2a1(2xi=1x1i2i=1x1i2)+(ba+1)(2ai=1a1i2i=1a1i2)]

= 2 ∗ { 2 ∑ x = 2 a − 1 [ x ∗ x ( x − 1 ) − ( x − 1 ) x ( 2 x − 1 ) 3 ] + ( b − a + 1 ) [ a ∗ a ( a − 1 ) − ( a − 1 ) a ( 2 a − 1 ) 3 ] } = 2*\{2\sum_{x = 2}^{a - 1}{[x*x(x-1) - \frac{(x-1)x(2x-1)}{3}]} + (b-a+1)[a*a(a-1)-\frac{(a-1)a(2a-1)}{3}]\} =2{2x=2a1[xx(x1)3(x1)x(2x1)]+(ba+1)[aa(a1)3(a1)a(2a1)]}

= 2 ∗ [ 2 3 ∑ x = 2 a − 1 ( x 3 − x ) + ( b − a + 1 ) ( a 3 3 − a 3 ) ] = 2*[\frac{2}{3}\sum_{x = 2}^{a - 1}{(x^3-x)} + (b-a+1)(\frac{a^3}{3}-\frac{a}{3})] =2[32x=2a1(x3x)+(ba+1)(3a33a)]

= 2 ∗ { 2 3 [ ∑ x = 1 a − 1 ( x 3 − x ) − ( 1 − 1 ) ] + ( b − a + 1 ) ( a 3 3 − a 3 ) } = 2*\{\frac{2}{3}[\sum_{x = 1}^{a - 1}{(x^3-x)}-(1 - 1)] + (b-a+1)(\frac{a^3}{3}-\frac{a}{3})\} =2{32[x=1a1(x3x)(11)]+(ba+1)(3a33a)}

= 2 ∗ [ 2 3 ( ∑ x = 1 a − 1 x 3 − ∑ x = 1 a − 1 x ) + ( b − a + 1 ) ( a 3 3 − a 3 ) ] = 2*[\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[32(x=1a1x3x=1a1x)+(ba+1)(3a33a)]

= 2 ∗ { 2 3 [ ( a − 1 ) a 2 ] 2 − a ( a − 1 ) 3 + ( b − a + 1 ) ( a 3 3 − a 3 ) } = 2*\{\frac{2}{3}[\frac{(a-1)a}{2}]^2-\frac{a(a-1)}{3} + (b-a+1)(\frac{a^3}{3}-\frac{a}{3})\} =2{32[2(a1)a]23a(a1)+(ba+1)(3a33a)}


t m p 2 = 2 ∑ i = 1 a − 1 i ( i + 1 ) + ( b − a ) ∗ a 2 tmp2=2\sum_{i = 1}^{a - 1}{i(i+1)}+(b-a)*a^2 tmp2=2i=1a1i(i+1)+(ba)a2

= 2 ( a − 1 ) a ( a + 1 ) 3 + b a 2 − a 3 =2\frac{(a-1)a(a+1)}{3}+ba^2-a^3 =23(a1)a(a+1)+ba2a3

= b a 2 − a 3 3 − 2 3 a =ba^2-\frac{a^3}{3}-\frac{2}{3}a =ba23a332a


那么tmp1和tmp2都可以 O ( 1 ) O(1) 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操场(数学,推公式)的全部内容,希望文章能够帮你解决所遇到的问题。

如果觉得如意编程网网站内容还不错,欢迎将如意编程网推荐给好友。