題目大意:統計位數不大於n的自守數的個數。
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
數據規模:1<=n<=2000。
理論基礎:
自守數:參見鏈接1。
性質定理1:一個數為自守數當且僅當它為一個自守數的後綴。
性質定理2:(1除外)n位數的自守數僅有兩個(位數包括前導0),優先考慮最高位不為0的時候。
題目分析:有了兩個性質定理以後我們可以知道,每個自守數都是已有的自守數+前綴數字而來的,所以只要知道n位的兩個自守數,就可以得到n+1位的兩個自守數。反過來思考,如果我們知道了n+1位的自守數後那麼小於n+1位的自守數我們都可以寫出來。這樣就出現了一個想法,先用遞歸將兩個兩千位(bign)(僅用到大數的乘法操作不是很困難)的自守數求出來,然後我們再找出值相同的自守數的個數m。用總數:1+2*n減去m即為答案了。當然,打表肯定是最好啦。掃描前導零的個數即為重復的個數。
代碼如下:
#include<iostream> #include<cstdio> using namespace std; char number1[2001]= "0302695456948792438016548848805106486276062082716415913252360\ 9790500938385405426324719893931802209823600162545177681029159\ 3965045066578090330527721983852863418796455114247485363072354\ 5704904450912521423427595549184397398445871252869481982692702\ 9255264834903206526851272202961318699947776535481291519857640\ 4229681830917734452777232007376038258831727292795636574190144\ 4523595431910306357249617898820317578776106213770808096781137\ 4931911766563031490205784352509572880668464121069252802275061\ 2985116162063840067789794024490238751112586895345495148882006\ 7866770234100283954928297028644727362521753544319791185506815\ 7264858804852673871684804002188529473022223344541221328464844\ 1535937936631336044589403287234784019473575603613462120086753\ 7334691331433871735088021260028575298538664393102232655345477\ 6845029957025561658143370236502074744856814787872902092412582\ 9053012491246688683515876774998917686787157281349408792768945\ 2979709777230540335661882819870221063055796723980661119019774\ 4642421025136748701117131278125400133690086034889084364023875\ 7659368219796261819178335204927041993248752378258671482789053\ 4489744014261231703569954841949944461060814620725403655999827\ 1588356035049327795540741961849280952093753026852390937562839\ 1485716123673519706092242423987770075749557872715597674134589\ 9753769551586271888794151630756966881635215504889827170437850\ 8028434084412644126821848514157729916034497017892335796684991\ 4473895660019325458276780006183298544262328272575561107331606\ 9701586498422229125548572987933714786632317240551575610235254\ 3994999345608083801190741530060056055744818709692785099775918\ 0500754164285277081620113502468060581632761716767652609375280\ 5684421448619396049983447280672190667041724009423446619781242\ 6690787535944616698508064636137166384049029219341881909581659\ 5244778618461409128782984384317032481734288865727376631465191\ 0498802944796081467376050395719689371467180137561905546299681\ 4764263903953007319108169802938509890062166509580863811000557\ 423423230896109004106619977392256259918212890625",number2[2001]= "9697304543051207561983451151194893513723937917283584086747639\ 0209499061614594573675280106068197790176399837454822318970840\ 6034954933421909669472278016147136581203544885752514636927645\ 4295095549087478576572404450815602601554128747130518017307297\ 0744735165096793473148727797038681300052223464518708480142359\ 5770318169082265547222767992623961741168272707204363425809855\ 5476404568089693642750382101179682421223893786229191903218862\ 5068088233436968509794215647490427119331535878930747197724938\ 7014883837936159932210205975509761248887413104654504851117993\ 2133229765899716045071702971355272637478246455680208814493184\ 2735141195147326128315195997811470526977776655458778671535155\ 8464062063368663955410596712765215980526424396386537879913246\ 2665308668566128264911978739971424701461335606897767344654522\ 3154970042974438341856629763497925255143185212127097907587417\ 0946987508753311316484123225001082313212842718650591207231054\ 7020290222769459664338117180129778936944203276019338880980225\ 5357578974863251298882868721874599866309913965110915635976124\ 2340631780203738180821664795072958006751247621741328517210946\ 5510255985738768296430045158050055538939185379274596344000172\ 8411643964950672204459258038150719047906246973147609062437160\ 8514283876326480293907757576012229924250442127284402325865410\ 0246230448413728111205848369243033118364784495110172829562149\ 1971565915587355873178151485842270083965502982107664203315008\ 5526104339980674541723219993816701455737671727424438892668393\ 0298413501577770874451427012066285213367682759448424389764745\ 6005000654391916198809258469939943944255181290307214900224081\ 9499245835714722918379886497531939418367238283232347390624719\ 4315578551380603950016552719327809332958275990576553380218757\ 3309212464055383301491935363862833615950970780658118090418340\ 4755221381538590871217015615682967518265711134272623368534808\ 9501197055203918532623949604280310628532819862438094453700318\ 5235736096046992680891830197061490109937833490419136188999442\ 576576769103890995893380022607743740081787109376"; int main() { int n,cnt=0; scanf("%d",&n); for(int i=1999;i>=1999-(n-1);i--) { if(number1[i]=='0')cnt++; if(number2[i]=='0')cnt++; } printf("%d\n",2*n-cnt+1); return 0; }