| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 10521 | Accepted: 7477 |
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
Hint
As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by
.
Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:
.
Source
typedef struct Matrix
{
// Made by xiper , Last updata : 2015 / 6 / 14
int r , c , ele[][];
Matrix(const int & r , const int & c)
{
this->r = r , this->c = c; // i will not init for ele , u should do it
}
friend ostream& operator << (ostream & os,const Matrix & x)
{
for(int i = ; i < x.r ; ++ i)
{
for(int j = ; j < x.c ; ++ j)
os << x.ele[i][j] << " ";
os << endl;
}
return os;
}
Matrix operator * (const Matrix & x) const
{
if (c != x.r)
{
cout << "Error on Matrix operator * , (c1 != r1)" << endl;
return Matrix(,);
}
Matrix res(r,x.c);
for(int i = ; i < r ; ++ i)
for(int j = ; j < x.c ; ++ j)
{
int sum = ;
for(int k = ; k < c ; ++ k)
sum += ele[i][k]*x.ele[k][j];
res.ele[i][j] = sum;
}
return res;
}
Matrix operator * (const int & x ) const
{
Matrix res(r,c);
for(int i = ; i < r ; ++ i)
for(int j = ; j < c ; ++ j)
res.ele[i][j] = ele[i][j]*x;
return res;
}
Matrix operator + (const Matrix & x) const
{
if (x.r != r || x.c != c)
{
cout << "Error on Matrix operator + , (r1 != r2 || c1 != c2)" << endl;
return Matrix(,);
}
Matrix res(r,c);
for(int i = ; i < r ; ++ i)
for(int j = ; j < c ; ++ j)
res.ele[i][j] = ele[i][j] + x.ele[i][j];
return res;
}
Matrix operator - (const Matrix & x) const
{
if (x.r != r || x.c != c)
{
cout << "Error on Matrix operator + , (r1 != r2 || c1 != c2)" << endl;
return Matrix(,);
}
Matrix res(r,c);
for(int i = ; i < r ; ++ i)
for(int j = ; j < c ; ++ j)
res.ele[i][j] = ele[i][j] - x.ele[i][j];
return res;
}
void r_ope(int whichr , int num)
{
for(int i = ; i < c ; ++ i)
ele[whichr][i] += num;
}
void c_ope(int whichc , int num)
{
for(int i = ; i < r ; ++ i)
ele[i][whichc] += num;
}
void init(int x)
{
for(int i = ; i < r ; ++ i)
for(int j = ; j < c ; ++ j)
ele[i][j] = x;
}
void init_dig()
{
memset(ele,,sizeof(ele));
for(int i = ; i < min(r,c) ; ++ i)
ele[i][i] = ;
}
Matrix Mulite (const Matrix & x ,int mod) const
{
if (c != x.r)
{
cout << "Error on Matrix function Mulite(pow may be) , (c1 != r1)" << endl;
return Matrix(,);
}
Matrix res(r,x.c);
for(int i = ; i < r ; ++ i)
for(int j = ; j < x.c ; ++ j)
{
int sum = ;
for(int k = ; k < c ; ++ k)
sum += (ele[i][k]*x.ele[k][j]) % mod;
res.ele[i][j] = sum % mod;
}
return res;
}
Matrix pow(int n , int mod)
{
if (r != c)
{
cout << "Error on Matrix function pow , (r != c)" << endl;
return Matrix(,);
}
Matrix tmp(r,c);
memcpy(tmp.ele,ele,sizeof(ele));
Matrix res(r,c);
res.init_dig();
while(n)
{
if (n & )
res = res.Mulite(tmp,mod);
n >>= ;
tmp = tmp.Mulite(tmp,mod);
}
return res;
}
};
AC代码就不贴了（其实就几行。。）