題意：
? ? ?給你兩個(gè)矩陣，讓你求兩矩陣的乘積，然后3取余。矩陣是n*n的，n<=800

思路：
? ? ? ?如果什么都不考慮的話，矩陣的乘法是o(n^3)的，800*800*800 = 512000000，超時(shí)那是妥妥的，而且還用到取余，%這個(gè)東西在我的印象里是很費(fèi)時(shí)間的，回到這道題目，我們發(fā)現(xiàn)一個(gè)很關(guān)鍵的地方，就是%3，那么也就是說(shuō)只有0.1.2這三種狀態(tài)，這樣的話我們直接改變一下矩陣乘法的循環(huán)順序，然后每次跳過(guò)0，就可以節(jié)省1/3的時(shí)間了，然后就ac了，但是后來(lái)發(fā)現(xiàn)個(gè)很奇怪的地方就是如果不優(yōu)化0，只要改變一下循環(huán)順序也可以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]


上面第一種超時(shí)，第三種是優(yōu)化了0，也就是優(yōu)化掉了1/3的時(shí)間可以ac可以接受，但是接受不了的就是第二種為什么會(huì)ac，我后來(lái)查了寫(xiě)for循環(huán)的東西，知道了一點(diǎn)，
(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 ++)

在算法的角度去考慮，上面兩個(gè)的時(shí)間復(fù)雜度是一樣的，但是在匯編角度去考慮，（2）會(huì)比（1）快很多，至于為什么，我不是很懂匯編，所以不能用匯編來(lái)解釋，但是我猜測(cè)有可能是這樣，第一層循環(huán)跳到第二層循環(huán)的時(shí)候有一些操作a,（1）比（2）多做了很多操作a，其余的地方他倆用的時(shí)間一樣，這樣就可能造成（2）比（1）快《結(jié)論是對(duì)的，證明是自己瞎猜的》，估計(jì)這個(gè)題目也是因?yàn)轭?lèi)似于這樣的東西導(dǎo)致的第二種情況能ac<上面的這些都是我自己猜的，有了解的希望能給我留個(gè)言，我也學(xué)習(xí)學(xué)習(xí)>

#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\n" ,c.mat[i][j] % 3);else printf("%d " ,c.mat[i][j] % 3);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的hdu4920 矩阵乘法%3的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。