poj 3070 Fibonacci

题目链接：​​Fibonacci​​

题目大意：求斐波那契的第n项对10000求余

题目思路：构造矩阵后直接矩阵快速幂

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
const ll maxn = 3;
const ll MOD = 10000;
#define mod(x) ((x)%MOD)

struct mat{
ll m[maxn][maxn];
}unit;

mat operator *(mat a,mat b){
mat ret;
ll x;
for(ll i = 0;i < maxn;i++){
for(ll j = 0;j < maxn;j++){
x = 0;
for(ll k = 0;k < maxn;k++)
x += mod((ll)a.m[i][k]*b.m[k][j]);
ret.m[i][j] = mod(x);
}
}
return ret;
}

void init_unit(){
for(ll i = 0;i < maxn;i++)
unit.m[i][i] = 1;
return ;
}

mat pow_mat(mat a,ll n){
mat ret = unit;
while(n){
if(n&1) ret = ret*a;
a = a*a;
n >>= 1;
}
return ret;
}

int main(){
int n;
init_unit();
while(~scanf("%d",&n)&&n!=-1){
if(n == 0) puts("0");
else if(n == 1) puts("1");
else if(n == 2) puts("1");
else{
mat a,b;
b.m[0][0] = 1,b.m[0][1] = 1,b.m[0][2] = 0;
b.m[1][0] = 1,b.m[1][1] = 0,b.m[1][2] = 1;
b.m[2][0] = 0,b.m[2][1] = 0,b.m[2][2] = 0;


a.m[0][0] = 1,a.m[0][1] = 1,a.m[0][2] = 0;
b = pow_mat(b,n-2);
a = a*b;
printf("%lld\n",a.m[0][0]%MOD);
}
}
return 0;
}