题解：UVA10359 Tiling

#include<bits/stdc++.h>
using namespace std;
const int N=257,M=1007;
const double Pi=acos(-1.0);
int n,lg[M];
string dp[N];

string High_precision_addition(string a,string b){
	int ans[max(a.size(),b.size())+7]={0};
	if(a.size()>b.size())
		swap(a,b);
	while(a.size()<b.size())
		a='0'+a;
	for(int i=0;i<a.size();++i)
		ans[i]=(a[a.size()-i-1]-'0'+b[a.size()-i-1]-'0');
	for(int i=0;i<a.size();++i){
		ans[i+1]+=ans[i]/10;
		ans[i]%=10;
	}
	string res="";
	if(ans[a.size()])
		res+=char(ans[a.size()]+'0');
	for(int i=a.size()-1;i>=0;--i)
		res+=char(ans[i]+'0');
	return res;
}

void Fast_Fourier_Transform(int limit,complex<double> *a,int type){
	if(limit==1)
		return;
	complex<double> a1[limit>>1],a2[limit>>1];
	for(int i=0;i<limit;i+=2){
		a1[i>>1]=a[i];
		a2[i>>1]=a[i+1];
	}
	Fast_Fourier_Transform(limit>>1,a1,type);
	Fast_Fourier_Transform(limit>>1,a2,type);
	complex<double> w{1,0};
	complex<double> wn{cos(2*Pi/limit),type*sin(2*Pi/limit)};
	for(int i=0;i<limit>>1;++i,w*=wn){
		a[i]=a1[i]+a2[i]*w;
		a[i+(limit>>1)]=a1[i]-a2[i]*w;
	}
}

string High_precision_multiplication(string a,string b){
	complex<double> f[1<<(lg[max(a.size(),b.size())]+1)];
	complex<double> g[1<<(lg[max(a.size(),b.size())]+1)];
	int ans[M]={0};
	for(int i=1;i<=a.size();++i)
		f[i-1]=a[a.size()-i]-'0';
	for(int i=1;i<=b.size();++i)
		g[i-1]=b[b.size()-i]-'0';
	int lt=1;
	while(lt<=a.size()+b.size()-1)
		lt<<=1;
	Fast_Fourier_Transform(lt,f,1);
	Fast_Fourier_Transform(lt,g,1);
	for(int i=0;i<=lt;++i)
		f[i]*=g[i];
	Fast_Fourier_Transform(lt,f,-1);
	for(int i=0;i<=a.size()+b.size()-1;++i)
		ans[i]=(int)(f[i].real()/lt+0.5);
	for(int i=0;i<a.size()+b.size()-1;++i){
		ans[i+1]+=ans[i]/10;
		ans[i]=ans[i]%10;
	}
	string res="";
	bool flg=true;
	for(int i=a.size()+b.size()-1;i>=0;--i){
		if(flg&&!ans[i])
			continue;
		else{
			flg=false;
			res+=char(ans[i]+'0');
		}
	}
	return res;
}

int main(){
	dp[0]="1",dp[1]="1",dp[2]="3";
	for(int i=2;i<M;++i)
		lg[i]=lg[i>>1]+1;
	for(int i=3;i<=250;++i)
		dp[i]=High_precision_addition(dp[i-1],
		High_precision_multiplication("2",dp[i-2]));
    while(cin>>n)
		cout<<dp[n]<<"\n";
	return 0;
}