首页 > 代码库 > HDU 4965 Fast Matrix Caculation ( 矩阵乘法 + 矩阵快速幂 + 矩阵乘法的结合律 )
HDU 4965 Fast Matrix Caculation ( 矩阵乘法 + 矩阵快速幂 + 矩阵乘法的结合律 )
HDU 4965 Fast Matrix Calculation ( 矩阵乘法 + 矩阵快速幂 + 矩阵乘法的结合律 )
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define MAX_SIZE 1001#define CLR( a, b ) memset( a, b, sizeof(a) )#define MOD 6typedef long long LL;LL A[MAX_SIZE][6] , B[6][MAX_SIZE], C[MAX_SIZE][6], D[MAX_SIZE][MAX_SIZE];LL n, k;struct Mat{ int n; LL mat[6][6]; Mat( int _n) { n = _n; CLR( mat, 0 ); } void zero() { CLR( mat, 0 ); } void init() { for( int i =0; i < n; ++i ) for( int j = 0; j < n; ++j ) mat[i][j] = ( i == j ); } Mat operator* ( const Mat &b ) const { Mat c( b.n ); for( int k = 0; k < n ; ++k ) for( int i = 0 ;i < n; ++i ) if( mat[i][k] ) for( int j = 0; j < n; ++j ) c.mat[i][j] = ( c.mat[i][j] + mat[i][k] * b.mat[k][j] ) % MOD; return c; } void debug() { for( int i = 0; i < n; ++i ) { for( int j = 0; j < n; ++j ) { if( j != 0 ) putchar( ‘ ‘ ); printf( "%I64d", mat[i][j] ); } putchar( ‘\n‘ ); } }};Mat fast_mod( Mat a, int b ){ Mat c( a.n ); c.init(); while( b ) { if( b & 1 ) c = c * a; a = a * a; b >>= 1; } return c;}void scan( LL &x ){ char c; while( c = getchar(), c < ‘0‘ || c > ‘9‘ ); x = c - ‘0‘; while( c = getchar(), c >= ‘0‘ && c <= ‘9‘ ) x = x * 10 + c -‘0‘;}int main(){ while( ~scanf( "%I64d %I64d", &n, &k ) && n + k ) { for( int i = 0; i < n; ++i ) for( int j = 0; j < k; ++j ) scan( A[i][j] ); for( int i = 0; i < k; ++i ) for( int j = 0; j < n; ++j ) scan( B[i][j] ); Mat t( k ); for( int i = 0; i < k; ++i ) for( int j = 0; j < k; ++j ) for( int y = 0; y < n; y++ ) t.mat[i][j] = ( t.mat[i][j] + B[i][y] * A[y][j] ) % MOD; t = fast_mod( t, n * n - 1 ); CLR( C, 0 ), CLR( D, 0 ); LL res = 0; for( int i = 0; i < n; ++i ) for( int j = 0; j < k; ++j ) for( int y = 0; y < k; y++ ) C[i][j] = ( C[i][j] + A[i][y] * t.mat[y][j] ) % MOD; for( int i = 0; i < n; ++i ) { for( int j = 0; j < n; ++j ) { for( int y = 0; y < k; y++ ) { D[i][j] = ( D[i][j] + C[i][y] * B[y][j] ) % 6; } res += D[i][j]; } } printf( "%I64d\n", res ); } return 0;}
HDU 4965 Fast Matrix Caculation ( 矩阵乘法 + 矩阵快速幂 + 矩阵乘法的结合律 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。