公式: f[i]=3*f[i-1]-f[i-2]+2
我自己是用了三个变量滚动。需要写一个高精度。
#include<cstdio>
#include<cstring>
struct Num{
int n,s[100005];
}f1,f2,f3;
int n;
void Do(){
f3.n=f2.n;
memset(f3.s,0,sizeof(f3.s));
for(int i=0;i<f2.n;i++){
f3.s[i]+=f2.s[i]*3;
if(f3.s[i]>9){
f3.s[i+1]+=f3.s[i]/10;
f3.s[i]%=10;
}
}
if(f3.s[f3.n]>0)f3.n++;
//printf("CTest2:%d%d\n",f2.s[0],f2.s[1]);
//printf("CTest3:%d%d\n",f3.s[0],f3.s[1]);
//printf("Test1:%d%d\n",f1.s[0],f1.s[1]);
f3.s[0]+=2-f1.s[0];
//printf("Test3:%d%d\n",f3.s[0],f3.s[1]);
if(f3.s[0]>9){
f3.s[1]+=f3.s[0]/10;
//printf("Test:%d%d\n",f3.s[0],f3.s[1]);
f3.s[0]%=10;
}
else if(f3.s[0]<0){
f3.s[1]--;
f3.s[0]+=10;
}
for(int i=1;i<f1.n;i++){
f3.s[i]-=f1.s[i];
if(f3.s[i]<0){
f3.s[i+1]--;
f3.s[i]+=10;
}
}
if(f3.s[f3.n-1]==0)f3.n--;
}
void Copy(){
f1.n=f2.n;
for(int i=0;i<f2.n;i++){f1.s[i]=f2.s[i];}
f2.n=f3.n;
for(int i=0;i<f3.n;i++){f2.s[i]=f3.s[i];}
}
int main(){
freopen("1002.in","r",stdin);
freopen("1002.out","w",stdout);
scanf("%d",&n);
if(n==1){printf("1\n");return 0;}
if(n==2){printf("5\n");return 0;}
f1.n=1;
f1.s[0]=1;
f2.n=1;
f2.s[0]=5;
n-=2;
while(n--){
Do();
Copy();
}
for(int i=f2.n-1;i>=0;i--){
printf("%d",f2.s[i]);
}
putchar('\n');
return 0;
}
评论 (0)
