题目背景 ​91029102 年 99 月 11 日，百度在 X 市 XX 中学举办了一场 AI 知识小课堂，本场 AI 知识小课堂老师教授了一些矩阵的相关知识，因为矩阵在 AI 人工智能中也有相当的应用。

题目描述 一个同学 LSQ 在小课堂后对矩阵产生极大的感兴趣，他想到了一个对矩阵求和的问题，但是这个矩阵实在太大了，他算不过来，你能帮帮他吗？

这个矩阵长这个样子，其右方和下方是没有边界的，但是不要担心，他并不要求你对整个矩阵求和，他只想知道，第 a 行第 c 列的格子为左上，第 b 行第 d 列的格子为右下的子矩阵中所有元素的和是多少？

方便起见，请将答案乘 2，再对 332748118 取模后输出

1    2    3    4    5    6    7    8    9    ... 2    3    4    5    6    7    8    9    10    ... 3    4    5    6    7    8    9    10    11    ... 4    5    6    7    8    9    10    11    12    ... 5    6    7    8    9    10    11    12    13    ... 6    7    8    9    10    11    12    13    14    ... 7    8    9    10    11    12    13    14    15    ... 8    9    10    11    12    13    14    15    16    ... 9    10    11    12    13    14    15    16    17    ... ...    ...    ...    ...    ...    ...    ...    ...    ...    ... 输入格式 一行四个正整数 a,b,c,d。

输出格式 一行一个整数表示答案。

数据范围 a<b\le 10^{18},c<d\le 10^{18}a<b≤10 18,c<d≤10 18 。

输出时每行末尾的多余空格，不影响答案正确性

样例输入 1 3 4 6 样例输出 108

 

 

思路1：(a,c)是起点坐标,(b,d)是终点坐标，先用等差计算第一行的和，在用等差计算所有行的和。起点的数是（a+c-1）,第一行终点的数是(a+d-1)，第一行的和是(（a+c-1）+ (a+d-1))*(d-c+1)  /2,以后每一行比前一行大（d-c+1）个。

AC代码：（将能加的同余定理都加上）

#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <sstream> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <stack> #include <queue> #include <map> #include <set> #define MAX 0x3f3f3f3f #define fori(a,b) for(int i=a;i<=b;i++) #define forj(a,b) for(int j=a;j<=b;j++) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const double PI = acos(-1); const int M=332748118; const int mod=1e9+7; int main() { long long a,b,c,d,h=0,w=0,start=0,s=0,ans=0; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); start=((a%M+c%M)%M-1)%M; if(start<0) start+=M; h=((b%M-a%M)%M+1)%M; if(h<0) h+=M; w=((d%M-c%M)%M+1)%M; if(w<0) w+=M; s=(((((a%M+c%M)%M-1)%M+(a%M+d%M)%M-1)%M)%M*(w%M))%M; if(s<0) s+=M; ans=(h%M*((s%M+(h-1)%M*w%M)%M)%M)%M; if(ans<0) ans+=M; printf("%lld\n",ans); return 0; } /*去掉同余定理的，方便看，但答案不对 #include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <sstream> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <stack> #include <queue> #include <map> #include <set> #define MAX 0x3f3f3f3f #define fori(a,b) for(int i=a;i<=b;i++) #define forj(a,b) for(int j=a;j<=b;j++) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const double PI = acos(-1); const int M=332748118; const int mod=1e9+7; int main() { long long a,b,c,d,h=0,w=0,start=0,s=0,ans=0; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); start=a+c-1; h=b-a+1); w=d-c+1; s=(a+c-1+a+d-1)*w; ans=h*((s+(h-1)*w); printf("%lld\n",ans); return 0; } */

思路2：通过观察所列出的矩阵，可以发现左上角与右上角的和在矩阵中能找到成对一样的和，但有的在中间可能会出现一个是这个和一半的数，但题目说最后答案要乘2，所以可以把每一个数都当成这个和，最后乘以个数就可以了。

#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <sstream> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <stack> #include <queue> #include <map> #include <set> #define MAX 0x3f3f3f3f #define fori(a,b) for(int i=a;i<=b;i++) #define forj(a,b) for(int j=a;j<=b;j++) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const double PI = acos(-1); const int M=332748118; const int mod=1e9+7; int main() { long long a,b,c,d,h=0,w=0,start=0,ans=0,endd=0; scanf("%lld%lld%lld%lld",&a,&b,&c,&d); start=(a%M+c%M-1)%M; if(start<0) start+=M; endd=(b%M+d%M-1)%M; if(endd<0) endd+=M; h=(b%M-a%M+1)%M; if(h<0) h+=M; w=(d%M-c%M+1)%M; if(w<0) w+=M; ans=(h%M*w%M*(start%M+endd%M)%M)%M; if(ans<0) ans+=M; //cout<<start<<" "<<endd<<" "<<h<<" "<<w<<" "<<endl; printf("%lld\n",ans); return 0; }