hdu4920 Matrix multiplication 模3矩阵乘法

时间：2022-02-13 10:50:42

hdu4920

Matrix multiplication

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 568    Accepted Submission(s): 225

Problem Description
Given two matrices A and B of size n×n, find the product of them.
bobo hates big integers. So you are only asked to find the result modulo 3.
Input
The input consists of several tests. For each tests:
The first line contains n (1≤n≤800). Each of the following n lines contain n integers -- the description of the matrix A. The j-th integer in the i-th line equals Aij. The next n lines describe the matrix B in similar format (0≤Aij,Bij≤109).
Output
For each tests:
Print n lines. Each of them contain n integers -- the matrix A×B in similar format.
Sample Input
1
0
1
2
0 1
2 3
4 5
6 7
Sample Output
0
0 1
2 1
Author
Xiaoxu Guo (ftiasch)
Source
Recommend
We have carefully selected several similar problems for you:  4919 4918 4917 4916 4914

2014多校5的最水的题，我没做出来，怕了。

题意：给出两个n*n的矩阵A和B，求A*B结果矩阵，元素都模3，n<=800。

题解：矩阵乘法加剪枝（？）。

800*800的矩阵，多组数据，直接算是会超时得飞起来的，只有考虑模3的特殊性。

读入后每个元素模3，得到的矩阵里全是0,1,2，随机数据的话有三分之一是零，所以我们的矩阵乘法要用k i j的循环嵌套顺序，第二层里面发现A[i][k]==0时就continue，直接少一维，也就是1/3概率少一维。这个是这题最关键的一步，没想到这步的话，其他再怎么优化也没用（我们试过了……）。但没有这一步，只是改成kij的循环，也能过，因为kij循环时，最内层的C[i][j]+=A[i][k]*B[k][j]中的A[i][k]是不变的，能存在缓存中，比ijk每次都从内存或者更慢的缓存中取数快多了，我都怕。

另外运算时可以使用cal[i][j][k]提前计算好((i*j)+k)%3，矩阵乘法的时候直接用这个结果。

------------------------------其他------------------------------------

顺便说个笑话：为什么Dijkstra没发明Floyd算法？因为他是ijk不是kij……

比赛的时候我们做这题优化得飞起来，读入输出优化，gets按字符串读一行来处理，输出用putchar，乘法、取余运算用上面说的那步省掉，输出不用'0'+C[i][j]而用数组存好ch[0]='0'这样输出，就差用fread一次读多行了……可是就是TLE，因为我们没想到最关键那步……

代码：



裸奔代码（仅仅是改成kij，其他什么读入啊乘法运算啊全部没有优化，也能A）：






 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include<cstdio>

 #include<cmath>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<map>

 #include<set>

 #include<stack>

 #include<queue>

 using namespace std;

 #define ll __int64

 #define usint unsigned int

 #define mz(array) memset(array, 0, sizeof(array))

 #define minf(array) memset(array, 0x3f, sizeof(array))

 #define REP(i,n) for(int i=0;i<(n);i++)

 #define FOR(i,x,n) for(int i=(x);i<=(n);i++)

 #define RD(x) scanf("%d",&x)

 #define RD2(x,y) scanf("%d%d",&x,&y)

 #define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)

 #define WN(x) printf("%d\n",x);

 #define RE  freopen("D.in","r",stdin)

 #define WE  freopen("1.out","w",stdout)

 int n;

 const int maxn=;

 int A[maxn][maxn],B[maxn][maxn],C[maxn][maxn];

 int main() {

     int i,j,k;

     while(scanf("%d",&n)!=EOF) {

         for(i=; i<n; i++)

             for(j=; j<n; j++) {

                 scanf("%d",&A[i][j]);

                 A[i][j]%=;

             }

         for(i=; i<n; i++)

             for(j=; j<n; j++) {

                 scanf("%d",&B[i][j]);

                 B[i][j]%=;

             }

         mz(C);

         for(k=; k<n; k++)

             for(i=; i<n; i++) {

                 for(j=; j<n; j++) {

                     C[i][j]+=A[i][k]*B[k][j];

                 }

             }

         for(i=; i<n; i++) {

             for(j=; j<n-; j++) {

                 putchar(C[i][j]%+'');

                 putchar(' ');

             }

             putchar(C[i][n-]%+'');

             puts("");

         }

     }

     return ;

 }




相关文章