首页 > 代码库 > POJ 3233 - Matrix Power Series ( 矩阵快速幂 + 二分)
POJ 3233 - Matrix Power Series ( 矩阵快速幂 + 二分)
POJ 3233 - Matrix Power Series ( 矩阵快速幂 + 二分)
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;#define MAX_SIZE 30#define CLR( a, b ) memset( a, b, sizeof(a) )int MOD = 0;int n, k;struct Mat{ LL mat[MAX_SIZE][MAX_SIZE]; Mat() { CLR( mat, 0 ); } void zero() { CLR( mat, 0 ); } void setv( int v ) { for( int i = 0; i < n; ++i ) for( int j = 0; j < n; ++j ) mat[i][j] = v; } 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; for( int i = 0; i < n; ++i ) for( int j = 0; j < n; ++j ) c.mat[i][j] = ( mat[i][j] + b.mat[i][j] ) % MOD; return c; } Mat operator * ( const Mat &b ) const { Mat c; 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( "%lld", mat[i][j] ); } putchar( ‘\n‘ ); } }};Mat fast_mod( Mat a, int b ){ Mat res; res.init(); while( b ) { if( b & 1 ) res = res * a; a = a * a; b >>= 1; } return res;}Mat solve( Mat a, int b ){ if( b == 1 ) return a; Mat res; res.init(); res = res + fast_mod( a, b >> 1); res = res * solve( a, b >> 1 ); if( b & 1 ) res = res + fast_mod( a, b ); return res;}void Orz(){ while( ~scanf( "%d %d %d", &n, &k, &MOD ) ) { Mat c; for( int i = 0; i < n; ++i ) for( int j = 0; j < n; ++j ) scanf( "%d", &c.mat[i][j] ); Mat res = solve( c, k ); res.debug(); }}int main(){ Orz(); return 0;}
POJ 3233 - Matrix Power Series ( 矩阵快速幂 + 二分)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。