uva 10359 Tiling

本文主要是介绍uva 10359 Tiling，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题：
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;
}