poj 3070 Fibonacci (矩阵加速线性递推式)
题意：求f[n] % 10000,f为斐波那契数。
思路：按照题目给出的公式，或者按照加速线性递推式的方法都可以。。。
因为把模数的1E4手滑写成1E4+7结果调了半天也是没谁了呵呵呵呵。
1/* ***********************************************
2Author :111qqz
3Created Time :Tue 18 Oct 2016 01:18:40 AM CST
4File Name :code/poj/3070.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int MOD = 1E4;
34int n;
35struct Mat
36{
37 int mat[5][5];
38
39 void clear()
40 {
41 ms(mat,0);
42 }
43
44}M,M1;
45Mat operator * (Mat a,Mat b)
46{
47 Mat c;
48 c.clear();
49 for ( int i = 0 ; i < 2 ; i++)
50 for ( int j = 0 ; j < 2 ; j++)
51 for ( int k = 0 ; k < 2 ; k++)
52 c.mat[i][j] = (c.mat[i][j] + a.mat[i][k]*b.mat[k][j])%MOD;
53 return c;
54}
55Mat operator ^ (Mat a,int b)
56{
57 Mat c;
58 c.clear();
59 for ( int i = 0 ; i < 2 ; i++)
60 for ( int j = 0 ; j < 2 ; j++)
61 c.mat[i][j]=(i==j); //初始化为单位矩阵。
62 while (b>0)
63 {
64 if (b&1) c = c * a;
65 b = b >> 1;
66 a = a * a;
67 }
68 return c;
69}
70int main()
71{
72 #ifndef ONLINE_JUDGE
73 freopen("code/in.txt","r",stdin);
74 #endif
75
76 while (~scanf("%d",&n))
77 {
78 if (n==-1) break;
79 if (n==0)
80 {
81 printf("%d\n",0);
82 continue;
83 }
84 M.mat[0][0] = 0;
85 M.mat[0][1] = 1;
86 M.mat[1][0] = 1;
87 M.mat[1][1] = 1;
88 M1.mat[0][0] = 0;
89 M1.mat[1][0] = 1;
90 Mat ans;
91 ans.clear();
92 ans = (M ^ n )* M1;
93 printf("%d\n",ans.mat[0][0]);
94 }
95
96 #ifndef ONLINE_JUDGE
97 fclose(stdin);
98 #endif
99 return 0;
100}