In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles?
Here is a sample tiling of a 2x17 rectangle.
输入描述
Input is a sequence of lines, each line containing an integer nu 输出描述
For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.
输入例子
2
8
12
100
200
输出例子
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
#include <stdio.h>
#include <iostream>
using namespace std;
char ans[][100]={
"1",
"1",
"3",
"5",
"11",
"21",
"43",
"85",
"171",
"341",
"683",
"1365",
"2731",
"5461",
"10923",
"21845",
"43691",
"87381",
"174763",
"349525",
"699051",
"1398101",
"2796203",
"5592405",
"11184811",
"22369621",
"44739243",
"89478485",
"178956971",
"357913941",
"715827883",
"1431655765",
"2863311531",
"5726623061",
"11453246123",
"22906492245",
"45812984491",
"91625968981",
"183251937963",
"366503875925",
"733007751851",
"1466015503701",
"2932031007403",
"5864062014805",
"11728124029611",
"23456248059221",
"46912496118443",
"93824992236885",
"187649984473771",
"375299968947541",
"750599937895083",
"1501199875790165",
"3002399751580331",
"6004799503160661",
"12009599006321323",
"24019198012642645",
"48038396025285291",
"96076792050570581",
"192153584101141163",
"384307168202282325",
"768614336404564651",
"1537228672809129301",
"3074457345618258603",
"6148914691236517205",
"12297829382473034411",
"24595658764946068821",
"49191317529892137643",
"98382635059784275285",
"196765270119568550571",
"393530540239137101141",
"787061080478274202283",
"1574122160956548404565",
"3148244321913096809131",
"6296488643826193618261",
"12592977287652387236523",
"25185954575304774473045",
"50371909150609548946091",
"100743818301219097892181",
"201487636602438195784363",
"402975273204876391568725",
"805950546409752783137451",
"1611901092819505566274901",
"3223802185639011132549803",
"6447604371278022265099605",
"12895208742556044530199211",
"25790417485112089060398421",
"51580834970224178120796843",
"103161669940448356241593685",
"206323339880896712483187371",
"412646679761793424966374741",
"825293359523586849932749483",
"1650586719047173699865498965",
"3301173438094347399730997931",
"6602346876188694799461995861",
"13204693752377389598923991723",
"26409387504754779197847983445",
"52818775009509558395695966891",
"105637550019019116791391933781",
"211275100038038233582783867563",
"422550200076076467165567735125",
"845100400152152934331135470251",
"1690200800304305868662270940501",
"3380401600608611737324541881003",
"6760803201217223474649083762005",
"13521606402434446949298167524011",
"27043212804868893898596335048021",
"54086425609737787797192670096043",
"108172851219475575594385340192085",
"216345702438951151188770680384171",
"432691404877902302377541360768341",
"865382809755804604755082721536683",
"1730765619511609209510165443073365",
"3461531239023218419020330886146731",
"6923062478046436838040661772293461",
"13846124956092873676081323544586923",
"27692249912185747352162647089173845",
"55384499824371494704325294178347691",
"110768999648742989408650588356695381",
"221537999297485978817301176713390763",
"443075998594971957634602353426781525",
"886151997189943915269204706853563051",
"1772303994379887830538409413707126101",
"3544607988759775661076818827414252203",
"7089215977519551322153637654828504405",
"14178431955039102644307275309657008811",
"28356863910078205288614550619314017621",
"56713727820156410577229101238628035243",
"113427455640312821154458202477256070485",
"226854911280625642308916404954512140971",
"453709822561251284617832809909024281941",
"907419645122502569235665619818048563883",
"1814839290245005138471331239636097127765",
"3629678580490010276942662479272194255531",
"7259357160980020553885324958544388511061",
"14518714321960041107770649917088777022123",
"29037428643920082215541299834177554044245",
"58074857287840164431082599668355108088491",
"116149714575680328862165199336710216176981",
"232299429151360657724330398673420432353963",
"464598858302721315448660797346840864707925",
"929197716605442630897321594693681729415851",
"1858395433210885261794643189387363458831701",
"3716790866421770523589286378774726917663403",
"7433581732843541047178572757549453835326805",
"14867163465687082094357145515098907670653611",
"29734326931374164188714291030197815341307221",
"59468653862748328377428582060395630682614443",
"118937307725496656754857164120791261365228885",
"237874615450993313509714328241582522730457771",
"475749230901986627019428656483165045460915541",
"951498461803973254038857312966330090921831083",
"1902996923607946508077714625932660181843662165",
"3805993847215893016155429251865320363687324331",
"7611987694431786032310858503730640727374648661",
"15223975388863572064621717007461281454749297323",
"30447950777727144129243434014922562909498594645",
"60895901555454288258486868029845125818997189291",
"121791803110908576516973736059690251637994378581",
"243583606221817153033947472119380503275988757163",
"487167212443634306067894944238761006551977514325",
"974334424887268612135789888477522013103955028651",
"1948668849774537224271579776955044026207910057301",
"3897337699549074448543159553910088052415820114603",
"7794675399098148897086319107820176104831640229205",
"15589350798196297794172638215640352209663280458411",
"31178701596392595588345276431280704419326560916821",
"62357403192785191176690552862561408838653121833643",
"124714806385570382353381105725122817677306243667285",
"249429612771140764706762211450245635354612487334571",
"498859225542281529413524422900491270709224974669141",
"997718451084563058827048845800982541418449949338283",
"1995436902169126117654097691601965082836899898676565",
"3990873804338252235308195383203930165673799797353131",
"7981747608676504470616390766407860331347599594706261",
"15963495217353008941232781532815720662695199189412523",
"31926990434706017882465563065631441325390398378825045",
"63853980869412035764931126131262882650780796757650091",
"127707961738824071529862252262525765301561593515300181",
"255415923477648143059724504525051530603123187030600363",
"510831846955296286119449009050103061206246374061200725",
"1021663693910592572238898018100206122412492748122401451",
"2043327387821185144477796036200412244824985496244802901",
"40866547756423702889555920724008244***9970992489605803",
"8173309551284740577911184144801648979299941984979211605",
"16346619102569481155822368289603297958599883969958423211",
"32693238205138962311644736579206595917199767939916846421",
"65386476410277924623289473158413191834399535879833692843",
"130772952820555849246578946316826383668799071759667385685",
"261545905641111698493157892633652767337598143519334771371",
"523091811282223396986315785267305534675196287038669542741",
"1046183622564446793972631570534611069350392574077339085483",
"2092367245128893587945263141069222138700785148154678170965",
"4184734490257787175890526282138444277401570296309356341931",
"8369468980515574351781052564276888554803140592618712683861",
"16738937961031148703562105128553777109606281185237425367723",
"33477875922062297407124210257107554219212562370474850735445",
"66955751844124594814248420514215108438425124740949701470891",
"133911503688249189628496841028430216876850249481899402941781",
"267823007376498379256993682056860433753700498963798805883563",
"535646014752996758513987364113720867507400997927597611767125",
"1071292029505993517027974728227441735014801995855195223534251",
"2142584059011987034055949456454883470029603991710390447068501",
"4285168118023974068111898912909766940059207983420780894137003",
"8570336236047948136223797825819533880118415966841561788274005",
"17140672472095896272447595651639067760236831933683123576548011",
"34281344944191792544895191303278135520473663867366247153096021",
"68562689888383585089790382606556271040947327734732494306192043",
"137125379776767170179580765213112542081894655469464988612384085",
"274250759553534340359161530426225084163789310938929977224768171",
"548501519107068680718323060852450168327578621877859954449536341",
"1097003038214137361436646121704900336655157243755719908899072683",
"2194006076428274722873292243409800673310314487511439817798145365",
"4388012152856549445746584486819601346620628975022879635596290731",
"8776024305713098891493168973639202693241257950045759271192581461",
"17552048611426197782986337947278405386482515900091518542385162923",
"35104097222852395565972675894556810772965031800183037084770325845",
"70208194445704791131945351789113621545930063600366074169540651691",
"140416388891409582263890703578227243091860127200732148339081303381",
"280832777782819164527781407156454486183720254401464296678162606763",
"561665555565638329055562814312908972367440508802928593356325213525",
"1123331111131276658111125628625817944734881017605857186712650427051",
"2246662222262553316222251257251635889469762035211714373425300854101",
"4493324444525106632444502514503271778939524070423428746850601708203",
"8986648889050213264889005029006543557879048140846857493701203416405",
"17973297778100426529778010058013087115758096281693714987402406832811",
"35946595556200853059556020116026174231516192563387429974804813665621",
"71893191112401706119112040232052348463032385126774859949609627331243",
"143786382224803412238224080464104696926064770253549719899219254662485",
"287572764449606824476448160928209393852129540507099439798438509324971",
"575145528899213648952896321856418787704259081014198879596877018649941",
"1150291057798427297905792643712837575408518162028397759193754037299883",
"2300582115596854595811585287425675150817036324056795518387508074599765",
"4601164231193709191623170574851350301634072648113591036775016149199531",
"9202328462387418383246341149702700603268145296227182073550032298399061",
"18404656924774836766492682299405401206536290592454364147100064596798123",
"36809313849549673532985364598810802413072581184908728294200129193596245",
"73618627699099347065970729197621604826145162369817456588400258387192491",
"147237255398198694131941458395243209652290324739634913176800516774384981",
"294474510796397388263882916790486419304580649479269826353601033548769963",
"588949021592794776527765833580972838609161298958539652707202067097539925",
"1177898043185589553055531667161945677218322597917079305414404134195079851",
"2355796086371179106111063334323891354436645195834158610828808268390159701",
"4711592172742358212222126668647782708873290391668317221657616536780319403",
"9423184345484716424444253337295565417746580783336634443315233073560638805",
"18846368690969432848888506674591130835493161566673268886630466147121277611",
"37692737381938865697777013349182261670986323133346537773260932294242555221",
"75385474763877731395554026698364523341972646266693075546521864588485110443",
"150770949527755462791108053396729046683945292533386151093043729176970220885",
"301541899055510925582216106793458093367890585066772302186087458353940441771",
"603083798111021851164432213586916186735781170133544604372174916707880883541",
"1206167596222043702328864427173832373471562340267089208744349833415761767083"
};
int main(){
int n;
while(cin>>n)
cout<<ans[n]<<endl;
return 0;
}