题意
Language:Fibonacci
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 Stanford Local 2006 |
分析
照题意模拟即可。时间复杂度\(O(2^3 \log n)\)
代码
#include<iostream>
#include<cstring>
#define rg register
#define il inline
#define co const
template<class T>il T read(){
rg T data=0,w=1;
rg char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') w=-1;
ch=getchar();
}
while(isdigit(ch))
data=data*10+ch-'0',ch=getchar();
return data*w;
}
template<class T>il T read(rg T&x){
return x=read<T>();
}
typedef long long ll;
co int mod=10000;
int n;
void mul(int f[2],int a[2][2]){
int c[2];
memset(c,0,sizeof c);
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
c[j]=(c[j]+(ll)f[k]*a[k][j])%mod;
memcpy(f,c,sizeof c);
}
void mulself(int a[2][2]){
int c[2][2];
memset(c,0,sizeof c);
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int k=0;k<2;++k)
c[i][j]=(c[i][j]+(ll)a[i][k]*a[k][j])%mod;
memcpy(a,c,sizeof c);
}
int main(){
// freopen(".in","r",stdin),freopen(".out","w",stdout);
while(~read(n)){
int f[2]={0,1};
int a[2][2]={{0,1},{1,1}};
for(;n;n>>=1){
if(n&1) mul(f,a);
mulself(a);
}
printf("%d\n",f[0]);
}
return 0;
}