题意：给两个矩阵a， b, 计算矩阵a*b的结果对3取余。
分析：直接计算时间复杂度是O(n^3),会超时，但是下面第一个代码勉强可以水过，数据的原因。
1 #include <iostream> 2 #include <cstdio> 3 #include <vector> 4 #include <cstring> 5 #include <cstdlib> 6 #include <algorithm> 7 const int maxn = 800+10; 8 using namespace std; 9 int n, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn]; 10 11 int main() 12 { 13 int i, j, k; 14 while(~scanf("%d", &n)) 15 { 16 memset(a, 0, sizeof(a)); 17 memset(b, 0, sizeof(b)); 18 memset(c, 0, sizeof(c)); 19 for(i = 0; i < n; i++) 20 for(j = 0; j < n; j++) 21 { 22 scanf("%d", &a[i][j]); 23 a[i][j] %= 3; 24 } 25 for(i = 0; i < n; i++) 26 for(j = 0; j < n; j++) 27 { 28 scanf("%d", &b[i][j]); 29 b[i][j] %= 3; 30 } 31 32 for(i = 0; i < n; i++) 33 { 34 for(k = 0; k < n; k++) 35 if(a[i][k]!=0) 36 for(j = 0; j < n; j++) 37 { 38 c[i][j] += a[i][k]*b[k][j]; 39 //c[i][j] %= 3; 加这个会超时 40 } 41 } 42 for(i = 0; i < n; i++) 43 { 44 for(j = 0; j < n; j++) 45 if(j == 0) 46 printf("%d", c[i][j]%3); 47 else 48 printf(" %d", c[i][j]%3); 49 printf(" "); 50 } 51 } 52 return 0; 53 }
再贴一个崔老师的代码：
他把所有的0都忽略了，很巧妙的优化，aa[][], bb[][]里存储的是下一个不为0的位置：
1 #include <iostream> 2 #include<stdio.h> 3 #include<vector> 4 #include<queue> 5 #include<stack> 6 #include<string.h> 7 #include<algorithm> 8 #include<map> 9 using namespace std; 10 #define LL long long 11 #define gcd(a,b) (b==0?a:gcd(b,a%b)) 12 #define lcm(a,b) (a*b/gcd(a,b)) 13 //O（n）求素数，1-n的欧拉数 14 #define N 100010 15 //A^x = A^(x % Phi(C) + Phi(C)) (mod C) 16 int a[880][880]; 17 int b[880][880]; 18 int aa[880][880]; 19 int bb[880][880]; 20 int c[880][880]; 21 int main() 22 { 23 int n; 24 while(~scanf("%d",&n)) 25 { 26 memset(a,0,sizeof(a)); 27 memset(b,0,sizeof(b)); 28 memset(aa,0,sizeof(aa)); 29 memset(bb,0,sizeof(bb)); 30 memset(c,0,sizeof(c)); 31 for(int i=1;i<=n;i++) 32 { 33 for(int j=1;j<=n;j++) 34 { 35 scanf("%d",&a[i][j]); 36 a[i][j]%=3; 37 } 38 } 39 for(int i=1;i<=n;i++) 40 { 41 for(int j=1;j<=n;j++) 42 { 43 scanf("%d",&b[i][j]); 44 b[i][j]%=3; 45 } 46 } 47 for(int i=1;i<=n;i++) 48 { 49 int x=-1; 50 for(int j=n;j>=0;j--) 51 { 52 aa[i][j]=x; 53 if(a[i][j])x=j; 54 } 55 } 56 for(int i=1;i<=n;i++) 57 { 58 int x=-1; 59 for(int j=n;j>=0;j--) 60 { 61 bb[i][j]=x; 62 if(b[i][j])x=j; 63 } 64 } 65 for(int i=1;i<=n;i++) 66 { 67 for(int j=aa[i][0];j!=-1;j=aa[i][j]) 68 { 69 for(int k=bb[j][0];k!=-1;k=bb[j][k]) 70 c[i][k]+=a[i][j]*b[j][k]; 71 } 72 } 73 for(int i=1;i<=n;i++) 74 { 75 for(int j=1;j<=n;j++) 76 { 77 printf("%d",c[i][j]%3); 78 if(j!=n)printf(" "); 79 else printf(" "); 80 } 81 } 82 } 83 return 0; 84 }