2901: 矩阵求和
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 411 Solved: 216[][][]Description
给出两个n*n的矩阵,m次询问它们的积中给定子矩阵的数值和。
Input
第一行两个正整数n,m。
接下来n行,每行n个非负整数,表示第一个矩阵。
接下来n行,每行n个非负整数,表示第二个矩阵。
接下来m行,每行四个正整数a,b,c,d,表示询问第一个矩阵与第二个矩阵的积中,以第a行第b列与第c行第d列为顶点的子矩阵中的元素和。
Output
对每次询问,输出一行一个整数,表示该次询问的答案。
Sample Input
3 2 1 9 8 3 2 0 1 8 3 9 8 4 0 5 15 1 9 6 1 1 3 3 2 3 1 2
Sample Output
661 388 【数据规模和约定】 对30%的数据满足,n <= 100。 对100%的数据满足,n <= 2000,m <= 50000,输入数据中矩阵元素 < 100,a,b,c,d <= n。
HINT
Source
经典题目,然后我忘了怎么做了,然后就被高一学长教做人了……
不妨设答案为乘积矩阵的第a行到第c行,第b行到第d行的元素之和。
$$\sum_{i=a}^{c} \sum_{j=b}^{d} \sum_{k=1}^{n} A_{i,k}B_{k,j}$$
$$\sum_{k=1}^{n} \sum_{i=a}^{c} \sum_{j=b}^{d} A_{i,k}B_{k,j}$$
$$\sum_{k=1}^{n} (\sum_{i=a}^{c}{A_{i,k}}) (\sum_{j=b}^{d}{B_{k,j}})$$
然后对两个矩阵进行前缀和预处理,每次查询的时候暴力枚举k就可以。卡常技巧也是很重要的……
1 #include2 3 #define siz (1 << 20) 4 #define frd fread(hd = buf, 1, siz, stdin) 5 #define gtc (hd == tl ? (frd, *hd++) : *hd++) 6 7 char buf[siz]; 8 char *hd = buf + siz; 9 char *tl = buf + siz;10 11 inline int nextInt(void)12 {13 int r = 0, c = gtc;14 15 for (; c < 48; c = gtc);16 17 for (; c > 47; c = gtc)18 r = r * 10 + c - '0';19 20 return r;21 }22 23 #undef siz24 #undef frd25 #undef gtc26 27 #define mxn 200528 #define mxm 5000529 #define lnt long long30 #define rnt register int31 32 int n, m;33 lnt A[mxn][mxn];34 lnt B[mxn][mxn];35 36 signed main(void)37 {38 #ifndef ONLINE_JUDGE39 freopen("in", "r", stdin);40 #endif41 42 n = nextInt();43 m = nextInt();44 45 for (rnt i = 1; i <= n; ++i)46 for (rnt j = 1; j <= n; ++j)47 A[i][j] = nextInt() + A[i - 1][j];48 49 for (rnt i = 1; i <= n; ++i)50 for (rnt j = 1; j <= n; ++j)51 B[i][j] = nextInt() + B[i][j - 1];52 53 while (m--)54 {55 static int a, b, c, d;56 57 a = nextInt();58 c = nextInt();59 b = nextInt();60 d = nextInt();61 62 #define swap(x, y) (x ^= y ^= x ^= y)63 64 if (a > b)swap(a, b);65 if (c > d)swap(c, d); 66 67 lnt ans = 0;68 69 for (rnt k = 1; k <= n; ++k)70 ans += (A[b][k] - A[a - 1][k]) * (B[k][d] - B[k][c - 1]);71 72 printf("%lld\n", ans);73 }74 }
@Author: YouSiki