毕业生对于网站建设感受,企业年报,h5游戏网站建设,免费云主机网址题目传送门 1 /*2 矩阵快速幂#xff1a;求第n项的Fibonacci数#xff0c;转置矩阵都给出#xff0c;套个模板就可以了。效率很高啊3 */4 #include cstdio5 #include algorithm6 #include cstring7 #include cmath8 using namespace st… 题目传送门 1 /*2 矩阵快速幂求第n项的Fibonacci数转置矩阵都给出套个模板就可以了。效率很高啊3 */4 #include cstdio5 #include algorithm6 #include cstring7 #include cmath8 using namespace std;9
10 const int MAXN 1e3 10;
11 const int INF 0x3f3f3f3f;
12 const int MOD 10000;
13 struct Mat {
14 int m[2][2];
15 };
16
17 Mat multi_mod(Mat a, Mat b) {
18 Mat ret; memset (ret.m, 0, sizeof (ret.m));
19 for (int i0; i2; i) {
20 for (int j0; j2; j) {
21 for (int k0; k2; k) {
22 ret.m[i][j] (ret.m[i][j] a.m[i][k] * b.m[k][j]) % MOD;
23 }
24 }
25 }
26 return ret;
27 }
28
29 int matrix_pow_mod(Mat x, int n) {
30 Mat ret; ret.m[0][0] ret.m[1][1] 1; ret.m[0][1] ret.m[1][0] 0;
31 while (n) {
32 if (n 1) ret multi_mod (ret, x);
33 x multi_mod (x, x);
34 n 1;
35 }
36 return ret.m[0][1];
37 }
38
39 int main(void) { //POJ 3070 Fibonacci
40 int n;
41 while (scanf (%d, n) 1) {
42 if (n -1) break;
43 Mat x;
44 x.m[0][0] x.m[0][1] x.m[1][0] 1; x.m[1][1] 0;
45 printf (%d\n, matrix_pow_mod (x, n));
46 }
47
48 return 0;
49 } 转载于:https://www.cnblogs.com/Running-Time/p/4693092.html
