首页 > 代码库 > Codeforces 450B - Jzzhu and Sequences ( 矩阵快速幂 )
Codeforces 450B - Jzzhu and Sequences ( 矩阵快速幂 )
Codeforces 450B - Jzzhu and Sequences ( 矩阵快速幂 )
题意：
给定f1和f2，求fn
分析:
特判f1,f2
当n>=3时使用矩阵快速幂即可( 简单题 )
将公式转化一下 , 可以得到一个变换矩阵
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define CLR( a, b ) memset( a, b, sizeof(a) )#define MAT_SIZE 2#define MOD 1000000007typedef long long LL;struct Mat{ LL mat[MAT_SIZE][MAT_SIZE]; void zero() { for( int i = 0; i < MAT_SIZE; ++i ) for( int j = 0; j < MAT_SIZE; ++j ) mat[i][j] = 0; } void init() { for( int i = 0; i < MAT_SIZE; ++i ) for( int j = 0; j < MAT_SIZE; ++j ) mat[i][j] = ( i == j ); } void setv( int v ) { for( int i = 0; i < MAT_SIZE; ++i ) for( int j = 0; j < MAT_SIZE; ++j ) mat[i][j] = v; } Mat operator*( const Mat &b)const { Mat c; c.zero(); for( int i =0; i < MAT_SIZE; ++i ) for( int j =0; j < MAT_SIZE; ++j ) for( int k = 0; k < MAT_SIZE; ++k ) c.mat[i][j] = ( c.mat[i][j] + mat[i][k] * b.mat[k][j] ) % MOD; return c; } };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;}void Orz(){ int n; LL x, y; while( ~scanf( "%lld %lld %d", &x, &y, &n ) ) { if( n == 1 ) printf( "%lld\n", ( x % MOD + MOD ) % MOD ); else if( n == 2 ) printf( "%lld\n", ( y % MOD + MOD ) % MOD ); else { Mat t; t.mat[0][0] = 0; t.mat[0][1] = 1; t.mat[1][0] = -1; t.mat[1][1] = 1; t = fast_mod( t, n-2 ); LL res = ( ( t.mat[1][0] * x + t.mat[1][1] * y ) % MOD + MOD ) % MOD; printf( "%lld\n", res ); } }}int main(){ Orz(); return 0;}
Codeforces 450B - Jzzhu and Sequences ( 矩阵快速幂 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。