poj 3070 Fibonacci

【题目】

Fibonacci

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 15088 Accepted: 10595

Description

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.

Input

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.

Output

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).

Sample Input 0 9 999999999 1000000000 -1

Sample Output 0 34 626 6875

---

【分析】

深夜做板子题 构造转移矩阵，快速幂一波

---

【代码】

//poj 3070 #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(int i=j;i<=k;i++) using namespace std; const int mod=10000; int n,m,T; struct matrix { int a[3][3]; matrix operator * (const matrix &x) const { matrix res; fo(i,1,2) fo(j,1,2) { res.a[i][j]=0; fo(k,1,2) res.a[i][j]=(res.a[i][j]+a[i][k]*x.a[k][j])%mod; } return res; } }x,ans; int main() { while(scanf("%d",&m) && m!=-1) { if(m==0) {puts("0");continue;} x.a[1][1]=0,x.a[1][2]=1,x.a[2][1]=1,x.a[2][2]=1; ans.a[1][1]=1,ans.a[1][2]=1,ans.a[2][1]=0,ans.a[2][2]=0; m--; while(m) { if(m&1) ans=ans*x; x=x*x,m>>=1; } printf("%d\n",ans.a[1][1]); } return 0; }