本文主要是介绍【HDU】4965 Fast Matrix Calculation 矩阵快速幂，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：【HDU】4965 Fast Matrix Calculation
题目分析：因为比赛的时候写的太匆忙。。写的不堪入目，所以赛后重写了一次，顺便就贴一下了。
因为A*B=C，所以C^(N*N-1) = A*B*A*B*A*...*B*A*B，因为满足结合律所以变成A*( (B*A)^(N*N-2) )*B，因为中间得到的矩阵最大不超过K(K<=6)，所以可以对中间的矩阵快速幂，然后再暴力和左右两边的矩阵相乘即可。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define FFF( a , b , c ) REP ( i , 0 , a ) REP ( j , 0 , b ) REP ( k , 0 , c )
#define FF( a , b ) REP ( i , 0 , a ) REP ( j , 0 , b )const int MAXN = 1005 ;
const int K = 6 ;int A[MAXN][K] , B[K][MAXN] , C[K][K] ;
int tmp1[MAXN][K] , tmp2[MAXN][MAXN] ;
int res[K][K] , mat[K][K] ;
int n , m ;void solve () {int sum = 0 , nn = n * n - 1 ;CLR ( C , 0 ) ;CLR ( mat , 0 ) ;CLR ( tmp1 , 0 ) ;CLR ( tmp2 , 0 ) ;FF ( n , m ) scanf ( "%d" , &A[i][j] ) ;FF ( m , n ) scanf ( "%d" , &B[i][j] ) ;FFF ( m , m , n ) mat[i][j] = ( mat[i][j] + B[i][k] * A[k][j] ) % K ;REP ( i , 0 , m ) C[i][i] = 1 ;while ( nn ) {if ( nn & 1 ) {CLR ( res , 0 ) ;FFF ( m , m , m ) res[i][j] = ( res[i][j] + C[i][k] * mat[k][j] ) % K ;FF ( m , m ) C[i][j] = res[i][j] ;}CLR ( res , 0 ) ;FFF ( m , m , m ) res[i][j] = ( res[i][j] + mat[i][k] * mat[k][j] ) % K ;FF ( m , m ) mat[i][j] = res[i][j] ;nn >>= 1 ;}FFF ( n , m , m ) tmp1[i][j] = ( tmp1[i][j] + A[i][k] * C[k][j] ) % K ;FFF ( n , n , m ) tmp2[i][j] = ( tmp2[i][j] + tmp1[i][k] * B[k][j] ) % K ;FF ( n , n ) sum += tmp2[i][j] ;printf ( "%d\n" , sum ) ;
}int main () {while ( ~scanf ( "%d%d" , &n , &m ) && ( n || m ) ) solve () ;return 0 ;
}这篇关于【HDU】4965 Fast Matrix Calculation 矩阵快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
