#include<stdio.h>
int n;
int a[3000],b[3000],c[3000];
int main()
{
	scanf("%d",&n);
	if(n==1)
	{
	printf("1");
	return 0;
	}
	if(n==2)
	{
	printf("2");
	return 0;
	}
	a[1]=a[0]=b[0]=1;
	b[1]=2;
	for(int i=3;i<=n;i++)
	{
		for(int j=1;j<=c[0];j++)
		c[j]=0;
		int t[3000];
		for(int j=0;j<=b[0];j++)
		t[j]=b[j];
		for(int j=1;j<=b[0];j++)
		{
			b[j]*=2;
		}
		for(int j=1;j<=b[0];j++)
		{
			b[j+1]+=b[j]/10;b[j]%=10;
		}
		if(b[b[0]+1]!=0)	b[0]++;
		int len=a[0]>b[0]?a[0]:b[0];
		c[0]=len;
		for(int j=1;j<=len;j++)
		{
			c[j]+=a[j]+b[j];
			c[j+1]+=c[j]/10;
			c[j]%=10;
		}
		if(c[len+1]!=0)	c[0]++;
		for(int j=0;j<=t[0];j++)
		a[j]=t[j];
		for(int j=0;j<=c[0];j++)
		b[j]=c[j];
	}
	for(int i=c[0];i>=1;i--)
	printf("%d",c[i]);
	return 0;
}

首先，需要知道pell数列的定义

Pell数列a1, a2, a3, ...的定义是这样的，a1 = 1, a2 = 2, ... , an = 2 * an − 1 + an - 2 (n > 2)。

所以，可用递归求解

a[1] = 1;
a[2] = 2;
a[n] =  2 * a[i - 1] + a[i - 2]; 

最终代码

#include <iostream>//hetao3097453
using namespace std;
long long a[50];
int main()
{
    int n;
    cin >> n;
    a[1] = 1;
    a[2] = 2;
    for(int i = 3;i <= n;i++)
    {
        a[i] = 2 * a[i - 1] + a[i - 2];
    }
    cout << a[n];
    return 0;
}

(已AC,放心食用)

hetao3097453

2023-01-15