POJ 3233-行列乗算とその性質と最適化

もともと図论をやっていた…POJ 3613をやっていた…结局どうしようもなかった…ネットで解題レポートを検索してみた…Floyd+マトリックス乗算…マトリックス乗算は线代はとっくに学んでいたが…プログラムを书いたことがない..Matrix 67のhttp://www.matrix67.com/blog/archives/276 中の话はとてもはっきりしています...それから私が自分で书く时..乗算の时に间违いがないため..このように考えることができます..类比Floyd判断更新时の...i,j,kはそれぞれ行列と和の顺番を代表して...3阶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];  

Matrix 64大牛文章はマトリックス乗算の性質についてはっきり言った...一列のマトリックス乗算を直接計算よりも公因式計算の効率が高いことを提案した...だからマトリックス乗算をする時主な点は柔軟に公因式を抽出することである.
この问题に戻ります…まずA^1+A^2+A^3+.....A^k k 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
型取りは型取りをしてから加算をしたり、型取りをしてから乗算をしたりする結果は同じです.だから、この2つの性質に基づいて2つの再帰でこの問題を解決することができます.データの伝達を便利にするために、構造体を使ってマトリクスを保存します.
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("
");
        }
   } 
   return 0;   
}