原题： In how many ways can you tile a 2 × n rectangle by 2 × 1 or 2 × 2 tiles?Here is a sample tiling of a 2 × 17 rectangle. Input Input is a sequence of lines, each line containing an integer number 0 ≤ n ≤ 250. Output For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2 × n rectangle. Sample Input 2 8 12 100 200 Sample Output 3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251
中文： 给你一个宽2长n的长条，让你用2×2或者是1×2的砖块平铺，问有多少中铺砖方法。
#include <bits/stdc++.h> using namespace std; const int maxn=1000;/*精度位数*/ /*(必选)类与基础功能定义，用法类似于unsigned(非负)*/ class bign { friend istream& operator>>(istream&,bign&);/*输入运算符友元*/ friend ostream& operator<<(ostream&,const bign&);/*输出运算符友元*/ friend bign operator+(const bign&,const bign&);/*加号运算符友元*/ friend bign operator*(const bign&,const bign&);/*乘号运算符友元*/ friend bign operator*(const bign&,int);/*高精度乘以低精度乘法友元*/ friend bign operator-(const bign&,const bign&);/*减号运算符友元*/ friend bign operator/(const bign&,const bign&);/*除法运算符友元*/ friend bign operator%(const bign&,const bign&);/*模运算符友元*/ friend bool operator<(const bign&,const bign&);/*逻辑小于符友元*/ friend bool operator>(const bign&,const bign&);/*逻辑大于符友元*/ friend bool operator<=(const bign&,const bign&);/*逻辑小于等于符友元*/ friend bool operator>=(const bign&,const bign&);/*逻辑大于等于符友元*/ friend bool operator==(const bign&,const bign&);/*逻辑等符友元*/ friend bool operator!=(const bign&,const bign&);/*逻辑不等符友元*/ private: int len,s[maxn]; public: bign(){memset(s,0,sizeof(s));len=1;} bign operator=(const char* num) { int i=0,ol; ol=len=strlen(num); while(num[i++]=='0'&&len>1) len--; memset(s,0,sizeof(s)); for(i=0;i<len;i++) s[i]=num[ol-i-1]-'0'; return *this; } bign operator=(int num) { char s[maxn]; sprintf(s,"%d",num); *this=s; return *this; } bign(int num){*this=num;} bign(const char* num){*this=num;} string str() const { int i; string res=""; for(i=0;i<len;i++)res=char(s[i]+'0')+res; if(res=="")res="0"; return res; } }; /*(可选)基本逻辑运算符重载*/ bool operator<(const bign& a,const bign& b) { int i; if(a.len!=b.len)return a.len<b.len; for(i=a.len-1;i>=0;i--) if(a.s[i]!=b.s[i]) return a.s[i]<b.s[i]; return false; } bool operator>(const bign& a,const bign& b){return b<a;} bool operator<=(const bign& a,const bign& b){return !(a>b);} bool operator>=(const bign& a,const bign& b){return !(a<b);} bool operator!=(const bign& a,const bign& b){return a<b||a>b;} bool operator==(const bign& a,const bign& b){return !(a<b||a>b);} /*(可选)加法运算符重载*/ bign operator+(const bign& a,const bign& b) { int i,max=(a.len>b.len?a.len:b.len),t,c; bign sum; sum.len=0; for(i=0,c=0;c||i<max;i++) { t=c; if(i<a.len)t+=a.s[i]; if(i<b.len)t+=b.s[i]; sum.s[sum.len++]=t%10; c=t/10; } return sum; } /*(可选)乘法运算符重载(高精度乘高精度)*/ bign operator*(const bign& a,const bign& b) { int i,j; bign res; for(i=0;i<a.len;i++) { for(j=0;j<b.len;j++) { res.s[i+j]+=(a.s[i]*b.s[j]); res.s[i+j+1]+=res.s[i+j]/10; res.s[i+j]%=10; } } res.len=a.len+b.len; while(res.s[res.len-1]==0&&res.len>1)res.len--; if(res.s[res.len])res.len++; return res; } /*高精度乘以低精度(注意:必须是bign*int顺序不能颠倒,要么会与高精度乘高精度发生冲突*/ bign operator*(const bign& a,int b) { int i,t,c=0; bign res; for(i=0;i<a.len;i++) { t=a.s[i]*b+c; res.s[i]=t%10; c=t/10; } res.len=a.len; while(c!=0) { res.s[i++]=c%10; c/=10; res.len++; } return res; } /*(可选)减法运算符重载*/ bign operator-(const bign& a,const bign& b) { bign res; int i,len=(a.len>b.len)?a.len:b.len; for(i=0;i<len;i++) { res.s[i]+=a.s[i]-b.s[i]; if(res.s[i]<0) { res.s[i]+=10; res.s[i+1]--; } } while(res.s[len-1]==0&&len>1)len--; res.len=len; return res; } /*(可选)除法运算符重载(注意:减法和乘法运算和>=运算符必选)*/ bign operator/(const bign& a,const bign& b) { int i,len=a.len; bign res,f; for(i=len-1;i>=0;i--) { f=f*10; f.s[0]=a.s[i]; while(f>=b) { f=f-b; res.s[i]++; } } while(res.s[len-1]==0&&len>1)len--; res.len=len; return res; } /*(可选)模运算符重载(注意:减法和乘法运算和>=运算符必选)*/ bign operator%(const bign& a,const bign& b) { int i,len=a.len; bign res,f; for(i=len-1;i>=0;i--) { f=f*10; f.s[0]=a.s[i]; while(f>=b) { f=f-b; res.s[i]++; } } return f; } /*(可选)X等运算符重载(注意:X法必选)*/ bign& operator+=(bign& a,const bign& b) { a=a+b; return a; } bign& operator-=(bign& a,const bign& b) { a=a-b; return a; } bign& operator*=(bign& a,const bign& b) { a=a*b; return a; } bign& operator/=(bign& a,const bign& b) { a=a/b; return a; } /*可选前缀++/--与后缀++/--(注意:加法必选)*/ bign& operator++(bign& a) { a=a+1; return a; } bign& operator++(bign& a,int) { bign t=a; a=a+1; return t; } bign& operator--(bign& a) { a=a-1; return a; } bign& operator--(bign& a,int) { bign t=a; a=a-1; return t; } istream& operator>>(istream &in,bign& x) { string s; in>>s; x=s.c_str(); return in; } ostream& operator<<(ostream &out,const bign& x) { out<<x.str(); return out; } bign f[251]; int main() { ios::sync_with_stdio(false); f[0]=f[1]=1; for(int i=2;i<=250;i++) f[i]=f[i-1]+2*f[i-2]; int n; while(cin>>n) cout<<f[n]<<endl; return 0; }思路： 高精度，递推。 考虑长为n的铺法，等于f(n-1)加上一个1×2的竖条，再加上f(n-2)加上一个2×2或者两个横着放到1×2的横条。 f[n]=f[n-1]+f[n-2]*2
