Zhiwei Zhang included in Algorithm

2019-12-13 2019-12-13 276 words 2 minutes

Contents

Description

请输出$Fib(n) mod 10000$ $n \leq 1000000000$

Solution

由于$n$的范围在$1e9$直接递推铁TLE，考虑矩阵快速幂 Fibonacci数列有如下性质通过多次迭代算是个板子题吧，记得在WUST新生赛做过一道想矩阵快速幂的题，然而正解是找规律QAQ，在此贴个板子。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61


#include <cstdio>
#include <queue>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstring>
#include <string>
typedef long long LL;
const int MOD = 1e4;
using namespace std;

struct Matrix{
	LL m[2][2];
	void print(){
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++)
				cout << m[i][j] << ' ';
			cout << endl;	
		}
	
	}
} base, ans;

Matrix times(Matrix a, Matrix b) {
	Matrix ans;
	ans.m[0][1] = ans.m[0][0] = ans.m[1][0] = ans.m[1][1] = 0;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++)
				ans.m[i][j] = (ans.m[i][j] + a.m[i][k]*b.m[k][j])%MOD;
		}
	}
	return ans;
}

void Matrixpow(LL x) {
	base.m[0][0] = base.m[1][0] = base.m[0][1] = 1;
	base.m[1][1] = 0;
	ans.m[0][0] = ans.m[1][1] = 1;
	ans.m[0][1] = ans.m[1][0] = 0;
	while (x) {
		if (x&1){
			ans = times(ans, base);
		} 
		x >>= 1;
		base = times(base, base);
	}
}
LL N;
int main(){
	while (cin >> N) {
		if (N == -1) break;
		if (N == 0) {
			cout << "0" << endl;
			continue;
		}
		Matrixpow(N);
		cout << ans.m[0][1] % MOD << endl; 
	}	
	return 0;
}