首页 > 代码库 > fzoj--1683--矩阵快速幂

fzoj--1683--矩阵快速幂

2024-07-12 17:58:49   213人阅读

...起床了 先把这题给过了 还是今天凌晨留下来的....

刚开始真sb啊 以为矩阵构造出来不能进行快速幂运算的 一定要借助单位矩阵.....

一般你构造出来的时候 2个矩阵的行列不是全都相等的  为了方便运算 我们可以空余位置默认为0

反正我是这样解决的 ....好像这个解决方法有点渣 我也不清楚...

　　　　touch    me

 

 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 const int mod = 2009; 6  7 struct data 8 { 9     int m[4][4];10 }base,result;11 12 void init( )13 {14     memset( base.m , 0 , sizeof(base.m) );15     base.m[0][1] = base.m[1][2] = base.m[3][0] = base.m[3][3] = 1;16     base.m[2][0] = 7;17     base.m[2][1] = 2;18     base.m[2][2] = 3;19     20     memset( result.m , 0 , sizeof(result.m) );21     result.m[0][0] = 1;22     result.m[1][0] = 3;23     result.m[2][0] = 5;24     result.m[3][0] = 0;25 }26 27 data multi( data& p , data& q )//p--base q--result28 {29     data temp;30     for( int i = 0 ; i<4 ; i++ )31     {32         for( int j = 0 ; j<4 ; j++ )33         {34             temp.m[i][j] = 0;35             for( int k = 0 ; k<4 ; k++ )36             {37                 temp.m[i][j] = ( temp.m[i][j] + p.m[i][k]*q.m[k][j] ) %mod;38             }39         }40     }41     return temp;42 }43 44 int fastMod( int n )45 {46     while( n )47     {48         if( n&1 )49         {50             result = multi( base , result );51         }52         base = multi( base , base );53         n >>= 1;54     }55     return result.m[3][0];56 }57 58 int main()59 {60     int t , n;61     while( cin >> t )62     {63         for( int i = 1 ; i<=t ; i++ )64         {65             init();66             cin >> n;67             cout << "Case " << i << ": " << fastMod(n+1) << endl;68         }69     }70     return 0;71 }
View Code

 

 1 #include <iostream> 2 #include <cstring> 3 using namespace std; 4  5 const int mod = 2009; 6  7 struct data 8 { 9     int m[4][4];10     int mat[4][1];11 }base,result;12 13 void init( )14 {15     memset( base.m , 0 , sizeof(base.m) );16     base.m[0][1] = base.m[1][2] = base.m[3][0] = base.m[3][3] = 1;17     base.m[2][0] = 7;18     base.m[2][1] = 2;19     base.m[2][2] = 3;20     21     result.mat[0][0] = 1;22     result.mat[1][0] = 3;23     result.mat[2][0] = 5;24     result.mat[3][0] = 0;25 }26 27 data multi( data& p , data& q )//p--base q--result28 {29     data temp;30     for( int i = 0 ; i<4 ; i++ )31     {32         for( int j = 0 ; j<1 ; j++ )33         {34             temp.mat[i][j] = 0;35             for( int k = 0 ; k<4 ; k++ )36             {37                 temp.mat[i][j] = ( temp.mat[i][j] + p.m[i][k]*q.mat[k][j] ) %mod;38             }39         }40     }41     return temp;42 }43 44 data mul( data& p , data& q )//p--base q--base45 {46     data t;47     for( int i = 0 ; i<4 ; i++ )48     {49         for( int j = 0 ; j<4 ; j++ )50         {51             t.m[i][j] = 0;52             for( int k = 0 ; k<4 ; k++ )53             {54                 t.m[i][j] = ( t.m[i][j] + p.m[i][k]*q.m[k][j] ) %mod;55             }56         }57     }58     return t;59 }60 61 int fastMod( int n )62 {63     while( n )64     {65         if( n&1 )66         {67             result = multi( base , result );68         }69         base = mul( base , base );70         n >>= 1;71     }72     return result.mat[3][0];73 }74 75 int main()76 {77     int t , n;78     while( cin >> t )79     {80         for( int i = 1 ; i<=t ; i++ )81         {82             init();83             cin >> n;84             cout << "Case " << i << ": " << fastMod(n+1) << endl;85         }86     }87     return 0;88 }
View Code

速度上 后者更快点 可能是因为前面进行了 无谓的*0运算吧...

其实 可以通过二分 更加高效 我还没写过~

 

today:

　　　我不知道该说什么，我只是突然在那一刻很想念她　-------　


联系
我们