给你两个矩阵，让你求两矩阵的乘积，然后3取余。矩阵是n*n的，n<=800
思路：
如果什么都不考虑的话，矩阵的乘法是o(n^3)的，800*800*800 = 512000000，超时那是妥妥的，而且还用到取余，%这个东西在我的印象里是很费时间的，回到这道题目，我们发现一个很关键的地方，就是%3，那么也就是说只有0.1.2这三种状态，这样的话我们直接改变一下矩阵乘法的循环顺序，然后每次跳过0，就可以节省1/3的时间了，然后就ac了，但是后来发现个很奇怪的地方就是如果不优化0，只要改变一下循环顺序也可以ac,
TLE
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
for(k = 1 ;k <= n ;k ++)
c[i][j] = c[i][j] + a[i][k] * b[k][j]
AC
for(k = 1 ;k <= n ;k ++)
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= n ;j ++)
c[i][j] = c[i][j] + a[i][k] * b[k][j]
或者
for(k = 1 ;k <= n ;k ++)
for(i = 1 ;i <= n ;i ++)
if(a[i][k])
for(j = 1 ;j <= n ;j ++)
c[i][j] = c[i][j] + a[i][k] * b[k][j]
上面第一种超时，第三种是优化了0，也就是优化掉了1/3的时间可以ac可以接受，但是接受不了的就是第二种为什么会ac，我后来查了写for循环的东西，知道了一点，
(1)
for(i = 1 ;i <= 10000 ;i ++)
for(j = 1 ;j <= 100 ;j ++)
(2)
for(i = 1 ;i <= 100 ;i ++)
for(j = 1 ;j <= 10000 ;j ++)
在算法的角度去考虑，上面两个的时间复杂度是一样的，但是在汇编角度去考虑，（2）会比（1）快很多，至于为什么，我不是很懂汇编，所以不能用汇编来解释，但是我猜测有可能是这样，第一层循环跳到第二层循环的时候有一些操作a,（1）比（2）多做了很多操作a，其余的地方他俩用的时间一样，这样就可能造成（2）比（1）快《结论是对的，证明是自己瞎猜的》，估计这个题目也是因为类似于这样的东西导致的第二种情况能ac<上面的这些都是我自己猜的，有了解的希望能给我留个言，我也学习学习>
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<stdio.h> #include<string.h> typedef struct { int mat[810][810]; }A; A mat_mat(A a ,A b ,int n) { A c; memset(c.mat ,0 ,sizeof(c.mat)); for(int k = 1 ;k <= n ;k ++) for(int i = 1 ;i <= n ;i ++) { if(a.mat[i][k]) for(int j = 1 ;j <= n ;j ++) c.mat[i][j] = c.mat[i][j] + a.mat[i][k] * b.mat[k][j]; } return c; } A a ,b ,c; int main () { int n ,i ,j; while(~scanf("%d" ,&n)) { for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= n ;j ++) { scanf("%d" ,&a.mat[i][j]); a.mat[i][j] %= 3; } for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= n ;j ++) { scanf("%d" ,&b.mat[i][j]); b.mat[i][j] %= 3; } c = mat_mat(a ,b ,n); for(i = 1 ;i <= n ;i ++) for(j = 1 ;j <= n ;j ++) if(j == n) printf("%d " ,c.mat[i][j] % 3); else printf("%d " ,c.mat[i][j] % 3); } return 0; }