首页 > 代码库 > FZU 1911 Construct a Matrix ( 矩阵快速幂 + 构造 )
FZU 1911 Construct a Matrix ( 矩阵快速幂 + 构造 )
FZU 1911 Construct a Matrix ( 矩阵快速幂 + 构造 )
题意：需要构造一个矩阵满足如下要求：1.矩阵是一个S(N)*S(N)的方阵2.S(N)代表斐波那契数列的前N项和模上M3.矩阵只能由1, 0, -1组成4.矩阵每行每列的和不能相等Here, the Fibonacci numbers are the numbers in the followingsequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
分析：1.可以发现，如果S(N) 为奇数，无法构造，直接输出No2.可以用一个3*3的矩阵通过矩阵快速幂来解决斐波那契数列前N项和问题3.4. 这个倒是真的不知道怎么构造。。。FZU大神的构造方法，，太牛了上三角全为1下三角全为-1对角线为 1 0 交替
S(N) = 4，构造如下
1 1 1 1
1 1 0 -1
1 1 -1 -1
0 -1 -1 -1
代码
/* ***********************************************Problem :FZU 1911 Construct a MatrixFile Name :Author :Created Time :2014-10-21 13:58:53 ************************************************ */#include <cstdio>#include <cstring>#include <iostream>#include <vector>#include <list>#include <queue>#include <map>#include <string>#include <set>#include <algorithm>#include <cmath>#include <ctime>using namespace std;typedef long long LL;typedef unsigned long long ULL;#define CLR(a,b) memset( a, b, sizeof(a) )#define MAX_SIZE 3int m, n, r;int M[MAX_SIZE];inline void scan( int &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 zero() { for( int i = 0; i < 3; ++i ) for( int j = 0; j < 3; ++j ) mat[i][j] = 0; } void init() { for( int i = 0; i < 3; ++i ) for( int j = 0; j < 3; ++j ) mat[i][j] = ( i == j ); } void setv( int v ) { for( int i = 0; i < 3; ++i ) for( int j = 0; j < 3; ++j ) mat[i][j] = v; } Mat operator * (const Mat &b) const { Mat c; c.zero(); for( int k = 0; k < 3; ++k ) for( int i = 0; i < 3; ++i ) if( mat[i][k] ) for( int j = 0; j < 3; ++j ) c.mat[i][j] = ( c.mat[i][j] + mat[i][k] * b.mat[k][j] ) % m; return c; } void debug() { for( int i = 0; i < 3; ++i ) { for( int j = 0; j < 3; ++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;}void Orz(){ //freopen( "1.txt", "r", stdin ); //freopen( "2.txt", "w", stdout ); int cas = 0, t; scan( t ); while( t-- ) { scan( n ); scan( m ); if( n == 1 ) r = 1; else if( n == 2 ) r = 2 % m; else { Mat c; c.setv(1); c.mat[0][0] = c.mat[0][2] = c.mat[1][2] = 0; //c.debug(); c = fast_mod( c, n-2 ); //c.debug(); r = 0; M[0] = M[1] = 1, M[2] = 2; for( int i = 0; i < 3; ++i ) r = ( r + c.mat[2][i] * M[i] ) % m ; } printf( "Case %d: ", ++cas ); if( r == 0 || r & 1 ) puts( "No" ); else { puts( "Yes" ); int out[210][210]; for( int i = 0; i < r; ++i ) { for( int j = 0; j < r-i; ++j ) { out[i][j] = 1; } } for( int i = 0; i < r; ++i ) { for( int j = 0; j < i; ++j ) { out[i][r-1-j] = -1; } } int flag = 1; for( int i = 0; i < r; ++i ) { for( int j = 0; j < r; ++j ) { if( i == r - j - 1 ) { if( flag ) out[i][j] = 1; else out[i][j] = 0; flag ^= 1; } } } for( int i = 0; i < r; ++i ) { for( int j = 0; j < r ; ++j ) { if( j != 0 ) putchar( ‘ ‘ ); printf( "%d", out[i][j] ); } putchar( ‘\n‘ ); } } }}int main(){ Orz(); return 0;}
FZU 1911 Construct a Matrix ( 矩阵快速幂 + 构造 )
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。