[UVa] 10229 - Modular Fibonacci

題目網址: http://goo.gl/mEqWgC

題意:
(from luckycat)


解 法: 把 fibonacci number 的遞迴關係以矩陣的方式表示，接著用快速冪求解，詳細解法請參考http://www.mathblog.dk/uva-10229-modular-fibonacci/。

TAG: Math,

注意:使用 long long

程式碼:

	/**
	* Tittle: 10229 - Modular Fibonacci
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/22
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	typedef long long ll;
	struct Mat {
	ll data[2][2];
	Mat( ll a=0LL, ll b=0LL, ll c=0LL, ll d=0LL ) {
	data[0][0] = a;
	data[0][1] = b;
	data[1][0] = c;
	data[1][1] = d;
	}
	void output( void ) {
	printf( "\t%lld %lld\n", data[0][0], data[0][1] );
	printf( "\t%lld %lld\n", data[1][0], data[1][1] );
	}
	};
	// declarations
	ll n, m;
	ll mask;
	// functions
	Mat mult( const Mat &a, const Mat &b )
	{
	Mat ret = Mat();
	FOR( i, 0, 1 ) FOR( j, 0, 1 ) {
	FOR( k, 0, 1 ) {
	ret.data[i][j] += a.data[i][k]*b.data[k][j];
	ret.data[i][j] &= mask;
	}
	}
	return ret;
	}
	// main function
	int main( void )
	{
	Mat mat;
	Mat unit = Mat( 1, 1, 1, 0 );
	ll l;
	// input
	while( scanf( "%lld%lld", &n, &m )==2 ) {
	// solve
	mask = ( 1LL << m )-1LL;
	++n;
	mat = Mat( 1, 0, 0, 1 );
	for( l=(1LL<<31); l>0LL; l>>=1 ) {
	mat = mult( mat, mat );
	if( (l&n) )
	mat = mult( mat, unit );
	}
	// output
	printf( "%lld\n", mat.data[1][1] );
	}
	return 0;
	}

view raw 10229 - Modular Fibonacci.cpp hosted with ❤ by GitHub