首页 > 代码库 > Uva10689 Yet another Number Sequence ( 矩阵快速幂 )
Uva10689 Yet another Number Sequence ( 矩阵快速幂 )
Uva 10689 Yet another Number Sequence ( 矩阵快速幂 )
题意：就是矩阵快速幂，没什么好说的。
分析：其实还是斐波那契数列。只是最后对应的矩阵不是(1,1)是(a,b)了MOD = 1;for( int i = 0; i < m; ++i ) MOD *= 10;
代码
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;#define MAX_SIZE 2#define CLR( a, b ) memset( a, b, sizeof(a) )LL a, b, n, m, t, MOD;LL M[MAX_SIZE];inline 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‘;}struct Mat{ LL mat[MAX_SIZE][MAX_SIZE]; void init() { for( int i = 0; i < 2; ++i ) for( int j = 0; j < 2; ++j ) mat[i][j] = ( i == j ); } void zero() { for( int i = 0; i < 2; ++i ) for( int j = 0; j < 2; ++j ) mat[i][j] = 0; } void setv( int v ) { for( int i = 0; i < 2; ++i ) for( int j = 0; j < 2; ++j ) mat[i][j] = v; } Mat operator*( const Mat &b )const { Mat c; c.zero(); for( int k = 0; k < 2; ++k ) for( int i = 0; i < 2; ++i ) if( mat[i][k] ) for( int j = 0; j < 2; ++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 < 2; ++i ) { for( int j = 0; j < 2; ++j ) { if( j != 0 ) putchar( ‘ ‘ ); printf( "%lld", mat[i][j] ); } putchar( ‘\n‘ ); } }};Mat fast_mod( Mat a, LL b ){ Mat res; res.init(); while( b ) { if( b & 1 ) res = res * a; a = a * a; b >>= 1; } return res;}void Orz(){ Mat c; c.setv( 1 ); c.mat[0][0] = 0; //c.debug(); scan( t ); while( t-- ) { scan( a ), scan( b ), scan( n ), scan( m ); MOD = 1; for( int i = 0; i < m; ++i ) MOD *= 10; //M[0] = a, M[1] = b; if( n == 1) printf( "%lld\n", a % MOD ); else if( n == 2 ) printf( "%lld\n", b % MOD ); else { Mat res = fast_mod( c, n - 2 + 1 ); LL ans = ( res.mat[1][0] * a + res.mat[1][1] * b ) % MOD; printf( "%lld\n", ans ); } }}int main(){ Orz(); return 0;}
Uva10689 Yet another Number Sequence ( 矩阵快速幂 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。