题目大意：原题链接
有2×1和2×2两种规格的地板，现要拼2×n的形状，共有多少种情况，首先要做这道题目要先对递推有一定的了解。
解题思路：
1.假设我们已经铺好了2×（n-1）的情形，则要铺到2×n则只能用2×1的地板
2.假设我们已经铺好了2×（n-2）的情形，则要铺到2×n则可以选择1个2×2或两个2×1，故可能有下列三种铺法
其中要注意到第三个会与铺好2×（n-1）的情况重复，故不可取，故可以得到递推式
a[n]=2*a[n-2]+a[n-1];
然后就是高精度部分，可直接用高精度的模板
解法一：递推+高精度
#include<cstring>
#include<iostream>
using namespace std; const int Base=;
const int Capacity=; struct BigInt{
int Len;
int Data[Capacity];
BigInt():Len(){}
BigInt(const BigInt &V):Len(V.Len) {memcpy(Data,V.Data,Len*sizeof*Data);}
BigInt(int V):Len() {for(;V>;V/=Base) Data[Len++]=V%Base;}
BigInt &operator=(const BigInt &V) {Len=V.Len;memcpy(Data,V.Data,Len*sizeof*Data);return *this;}
int &operator[] (int Index) {return Data[Index];}
int operator[] (int Index) const {return Data[Index];}
}; BigInt operator+(const BigInt &A,const BigInt &B){
int i,Carry();
BigInt R;
for(i=;i<A.Len||i<B.Len||Carry>;i++){
if(i<A.Len) Carry+=A[i];
if(i<B.Len) Carry+=B[i];
R[i]=Carry%Base;
Carry/=Base;
}
R.Len=i;
return R;
} ostream &operator<<(ostream &Out,const BigInt &V){
int i;
Out<<(V.Len==?:V[V.Len-]);
for(i=V.Len-;i>=;i--)
for(int j=Base/;j>;j/=)
Out<<V[i]/j%;
return Out;
} int main()
{
int n;
BigInt a[];
a[]=,a[]=;
for(int i=;i<=;i++)
a[i]=a[i-]+a[i-]+a[i-];
while(cin>>n)
cout<<a[n]<<endl;
return ;
}
解法二：递推+String应用(模拟)
#include<cstring>
#include<iostream>
using namespace std;
int n;
string a[];
string Add(string s1,string s2)
{
if(s1.length()<s2.length())
swap(s1,s2);
for(int i=s1.length()-,j=s2.length()-;i>=;i--,j--){
s1[i]=s1[i]+(j>=?s2[j]-'':);//不够则补上前导零
if(s1[i]-''>=){//判断进位
s1[i]=(s1[i]-'')%+'';//加上字符'0'将s1[i]还原为字符
if(i) s1[i-]++;
else s1=''+s1;//分情况考虑进位加一
}
}
return s1;
}
int main()
{
a[]="",a[]="";
for(int i=;i<=;i++)
a[i]=Add(Add(a[i-],a[i-]),a[i-]);
while(cin>>n)
cout<<a[n]<<endl;
return ;
}