就是用f(n) = f(n-1) + f(n-2) * 2用递推写一下外加大数加法
还要注意f(0) = 1!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!他娘的


#include<iostream>
#include<Cstdio>
#include<Cstring>
using namespace std;


char A2[5000], A1[5000], Sum1[5000], Sum[5000];
void Add(char* A, char* B, char* result)
{
	int i = 0, j = 0, k, takeOver, temp1, temp2, sum;
	char temp;
	
	while (A[i] != '\0')
		++i;
	
	while(B[j] != '\0')
		++j;
	
	i--, j--, k = 0, takeOver = 0;
	
	while (i >= 0 || j >= 0)
	{
		if(i >= 0)
		{
			temp1 = A[i--] - '0';
		}
		else 
			temp1 = 0;
        if(j >= 0)
			temp2 = B[j--] - '0';
		else
			temp2 = 0;
		sum = temp1 + temp2 + takeOver;
		
		if(sum < 10)
		{
			result[k++] = sum + '0';
			takeOver = 0;
		}
		else
		{
			result[k++] = sum - 10 + '0';
			takeOver = 1;
		}
		
	}
	
	if(takeOver == 1)
		result[k++] = '1';
	
	
	i = 0, j = k - 1;
	while (i < j) 
	{
		temp = result[i];
		result[i] = result[j];
		result[j] = temp;
		i++; j--;
	}
	result[k] = '\0';
	
	
}

void copy(char* A, char* B)
{
	int i = 0;
	while(A[i] != '\0')
	{
		B[i] = A[i];
		i++;
	}
	B[i] = '\0';
}

void f(int n)
{
	if(n == 2)
	{
		Sum[0] = '3';
		Sum[1] = '\0';
		return;
	}
	if(n == 1)
	{
		Sum[0] = '1';
		Sum[1] = '\0';
		return;
	}
	
	if(n == 0)
	{
		Sum[0] = '1';
		Sum[1] = '\0';
		return;
	}

	A2[0] = '1';A2[1] = '\0';
	A1[0] = '3';A1[1] = '\0';
	
	for(int i = 3; i <= n; ++i)
	{
		Add(A2, A1, Sum1);
		Add(A2, Sum1, Sum);
		copy(A1, A2);
		copy(Sum, A1);
	}
	
}

int main()
{
	int m;
	while(cin >> m)
	{
	   memset(A1, '0', sizeof(A1));
	   memset(A2, '0', sizeof(A2));
	   memset(Sum1, '0', sizeof(Sum1));
	   memset(Sum, '0', sizeof(Sum));
	   f(m);
		printf("%s\n", Sum);
	}
   return 0;
}