Fibonacci（矩阵快速幂）

Fibonacci

时间限制: 1 Sec  内存限制: 128 MB

题目描述

In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
An alternative formula for the Fibonacci sequence is

Given an integer n, your goal is to compute the last 4 digits of Fn.
 

输入

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

输出

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

样例输入

复制样例数据

0
9
999999999
1000000000
-1

样例输出

0
34
626
6875

提示

As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

LL n;
const long long mod = 10000;

struct node
{
	LL m[3][3];
};

node mul(node x, node y){
	node res;
	memset(res.m, 0, sizeof(res.m));
	for (int i = 1; i <= 2; i++){
		for (int j = 1; j <= 2; j++){
			for (int k = 1; k <= 2; k++){
				res.m[i][j] = (res.m[i][j] + x.m[i][k] * y.m[k][j] % mod) % mod;
			}
		}
	}
	return res;
}

node pow_M(node x, LL num){
	node res;
	memset(res.m, 0, sizeof(res.m));
	for (int i = 1; i <= 2; i++) res.m[i][i] = 1;
	while(num){
		if(num & 1) res = mul(res, x);
		x = mul(x, x);
		num >>= 1LL;
	}
	return res;
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	while(scanf("%lld", &n) == 1){
		if(n == -1) break;
		if(n == 0){
			printf("0\n");
			continue;
		}else if(n == 1 || n == 2){
			printf("1\n");
		}
		node M;
		M.m[1][1] = 1, M.m[1][2] = 1, M.m[2][1] = 1, M.m[2][2] = 0;
		M = pow_M(M, n - 2);
		LL p = (M.m[1][1] + M.m[1][2]) % mod, ans = 0, num = 0, f = 1;
		while(p){
			if(++num > 4) break;
			ans += p % 10 * f;
			f *= 10;
			p /= 10;
		}
		printf("%lld\n", ans % mod);
	}

	return 0;
}
/**/