POJ 3233 - 矩陣乘法及其性質和優化

本來在做圖論...做POJ3613...結果怎麼搞都搞不出...到網上搜了下解題報告...Floyd+矩陣乘法...矩陣乘法雖然線代早學了..但寫程式沒用過..就看了下Matrix67的​​http://www.matrix67.com/blog/archives/276​​ 裡面說的很清楚了...然後我自己寫的時候..為了乘法時不寫錯..可以這麼想..類比Floyd判斷更新時的...i,j,k分别代表行列和做和的順序...三層1~N..

for (i=1;i<=n;i++) 
       for (j=1;j<=n;j++)    
         for (k=1;k<=n;k++)   
           h.s[i][j]+=a.s[i][k]*b.s[k][j];      

得到的矩陣點[ i ] [ j ]+=第一個矩陣[ i ] [ k ] * 第二個矩陣[ k ] [ j ] ...似想 line[ i -> j ] 由 k 點更新...思維就比較準确了..

        矩陣加法很簡單..a舉證和b舉證對應的點直接相加就是了...

for (i=1;i<=n;i++)
        for (j=1;j<=n;j++) 
           h.s[i][j]=a.s[i][j]+b.s[i][j];      

Matrix64大牛文章關于矩陣乘法的性質已經說得很清楚了...将一列矩陣乘法提出公因式計算的效率比直接算高很多...是以在做矩陣乘法時主要一點就是要靈活的提取公因式..

回到這道題...首先 A^1+A^2+A^3+.......A^k 若k%2==0 可分解為 ( A^1+A^2+A^3...A^(k/2-1) ) + A^(k/2)*( A^1+A^2+A^2+....A^k ) 若是k%2==1..則最後一項多出來...

        再一個求 A^k ..若 k 為偶數 A^k = A^(k/2) * A^(k/2) 若 k 為奇數 A^k = A^(k/2) * A^(k/2) *A

而取模在先取模再做加法或者先取模再做乘法結果是一樣的..是以可以根據這兩個性質用兩個遞歸來解決這個問題...為了友善資料傳遞..我使用結構體來存矩陣的..

Program:

// POJ3233 矩陣乘法優化A+A^2+....A^k % m 
#include<iostream>
using namespace std;
struct pp
{
    int s[32][32];     
}ans,a;
int n,k,m,i,j;
pp muti(pp a,pp b)
{
     int k,i,j;
     pp h;
     memset(h.s,0,sizeof(h.s));
     for (i=1;i<=n;i++) 
       for (j=1;j<=n;j++)    
         for (k=1;k<=n;k++)   
           h.s[i][j]+=(a.s[i][k]*b.s[k][j])%m;
     for (i=1;i<=n;i++)
       for (j=1;j<=n;j++) 
          h.s[i][j]%=m;
     return h;
}
pp add(pp a,pp b)
{
   pp h;
   int i,j;
   for (i=1;i<=n;i++)
     for (j=1;j<=n;j++) 
       h.s[i][j]=(a.s[i][j]+b.s[i][j])%m;   
   return h;         
}
pp find(int p)
{
   pp h,k;
   if (p==1) return a;  
   k=find(p/2);   
   if (p%2) h=muti(muti(k,k),a);        
   else h=muti(k,k);     
   return h;     
}
pp make(int p)
{
   int i,j;         
   pp h,k;   
   if (p==1) return a;  
   k=find(p/2); h=make(p/2);
   h=add(h,muti(k,h));  
   if (p%2)
   {
       k=find(p);
       h=add(h,k);      
   } 
   return h;   
}
int main()
{ 
   while (~scanf("%d%d%d",&n,&k,&m))
   {
        for (i=1;i<=n;i++)
          for (j=1;j<=n;j++) scanf("%d",&a.s[i][j]); 
        ans=make(k);
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++) printf("%d ",ans.s[i][j]);
            printf("\n");
        }
   } 
   return 0;   
}