POJ 3070 Fibonacci
リンク:http://poj.org/problem?id=3070
Fibonacci
Time Limit:1000 MSメモリLimit:65536 K
Total Submissions:10796 Acctepted:7678
Description
In the Fibonacci integer sequence,F 0=0,F 1=1,and Fn=Fn−1＋Fn−2 for n≧2.For example,the first tems of the Fibonacci sequence are:
0,1,2,3,5,8,13,21,34,…
An alternative formula for the Fibonacci sequence is
.
Gven an integer n,your goal is to computte 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-off-file is denoted bya 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 zros、print‘0’;others wise、omit any leading zros(i.e.print Fn mod 10000)
Sample Input
0 9999999,000-1
Sample Output
0 34 626 6875
ベント
As a reminder,marix multication is assicative,and the product of two 2× 2 matices is given by
.
Also、note that rasing any 2× 2 matix to the 0 th power gives the identity marix:
.
Source Stonford Local 2006の大意――Fibonacciの数列を解く公式をあげます.問:一つの数nを与えます.この式でF(n)の後四桁を計算してください.
考え方——テーマはもう私達にマトリクスで連続してFibonacci数を求めると教えました.問題はnが大きいので、直接行列でn-1回乗るなら、TLEを肯定します.したがって、二分割で素早くべき乗できます.
複雑度分析——時間複雑度:O(n)、空間複雑度:O(1)
ACコードを添付:
Fibonacci
Time Limit:1000 MSメモリLimit:65536 K
Total Submissions:10796 Acctepted:7678
Description
In the Fibonacci integer sequence,F 0=0,F 1=1,and Fn=Fn−1＋Fn−2 for n≧2.For example,the first tems of the Fibonacci sequence are:
0,1,2,3,5,8,13,21,34,…
An alternative formula for the Fibonacci sequence is
.Gven an integer n,your goal is to computte 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-off-file is denoted bya 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 zros、print‘0’;others wise、omit any leading zros(i.e.print Fn mod 10000)
Sample Input
0 9999999,000-1
Sample Output
0 34 626 6875
ベント
As a reminder,marix multication is assicative,and the product of two 2× 2 matices is given by
.Also、note that rasing any 2× 2 matix to the 0 th power gives the identity marix:
.Source Stonford Local 2006の大意――Fibonacciの数列を解く公式をあげます.問:一つの数nを与えます.この式でF(n)の後四桁を計算してください.
考え方——テーマはもう私達にマトリクスで連続してFibonacci数を求めると教えました.問題はnが大きいので、直接行列でn-1回乗るなら、TLEを肯定します.したがって、二分割で素早くべき乗できます.
複雑度分析——時間複雑度:O(n)、空間複雑度:O(1)
ACコードを添付:
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned int UI;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
const double PI = 3.14159265;
const double E = 2.71828182846;
const int MOD = 10000;
struct matrix
{
int mat[2][2];
} res, base; //
matrix mul(matrix a, matrix b); //
int fast_mod(int x); //
// a^n = (a^(n/2))^2 n
// a^n = a*(a^(n/2))^2 n
int main()
{
ios::sync_with_stdio(false);
int num;
while (cin >> num && num != -1)
{
cout << fast_mod(num) << endl;
}
return 0;
}
matrix mul(matrix a, matrix b)
{
matrix temp;
for (int i=0; i<2; ++i)
for (int j=0; j<2; ++j)
{
temp.mat[i][j] = 0;
for (int k=0; k<2; ++k)
temp.mat[i][j] = (temp.mat[i][j]+a.mat[i][k]*b.mat[k][j])%MOD;
}
return temp;
}
int fast_mod(int x)
{
base.mat[0][0]=base.mat[0][1]=base.mat[1][0]=1;
base.mat[1][1]=0; //
res.mat[0][0]=res.mat[1][1]=1;
res.mat[0][1]=res.mat[1][0]=0; //
while (x)
{
if (x & 1) // 2
{
res = mul(res, base);
}
base = mul(base, base);
x >>= 1; // 2
}
return res.mat[0][1];
}