收藏
关注1个长度为2N的数，如果左边N个数的和 = 右边N个数的和，那么就是一个幸运号码。
例如：99、1230、123312是幸运号码。
给出一个N，求长度为2N的幸运号码的数量。由于数量很大，输出数量 Mod 10^9 + 7的结果即可。
Input
输入N(1<= N <= 1000)
Output
输出幸运号码的数量 Mod 10^9 + 7
Input示例
1
Output示例
9
思路：就是简单的数位dp；
然而1000的话，我的程序会超时，我就打表了；
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<cstdio> #include<cmath> #include<string> #include<queue> #include<algorithm> #include<stack> #include<cstring> #include<vector> #include<list> #include<set> #include<map> using namespace std; #define ll long long #define pi (4*atan(1.0)) #define eps 1e-4 #define bug(x) cout<<"bug"<<x<<endl; const int N=2e3+10,M=9e3+10,inf=2147483647,mod=1e9+7; const ll INF=1e18+10; int f[N][M],bit[N]; int n; int dp(int pos,int sum,int flag,int p) { if(sum<0)return 0; if(pos==0)return (sum==0); if(flag&&f[pos][sum]!=-1)return f[pos][sum]; int x=flag?9:bit[pos]; int ans=0; for(int i=0;i<=x;i++) { if(!p&&!i)continue; ans+=dp(pos-1,sum+i*(pos>n?1:-1),flag||1<x,1); ans%=mod; } if(flag)f[pos][sum]=ans; return ans; } ll getans(int n) { for(int i=1;i<=2*n;i++) bit[i]=9; return dp(2*n,0,0,0); } int ans[N]={9,615,50412,4379055,392406145,866068521,483495549,523490719,800281947,430186565,561681616,220226100,161607248,925593556,311824908,178689147,908607107,365848725,97803955,63023696,429162151,911808347,750835988,120835572,809949499,111020821,453799486,726510366,226689578,549032435,616094021,144195347,898219964,743845697,59999210,155013039,759934049,731804472,89385845,657249105,228802926,152660313,233093079,704389580,209149562,964418519,939135180,473454567,862658993,172097799,382026529,407265970,575668268,998155863,265988895,659340773,163956486,871312886,298172468,901901791,160767603,14714589,982305699,669952960,278213790,257674660,411083381,497391575,142224880,330760496,828767974,499230492,98769274,732881836,450433863,618308311,6822325,932525789,400277298,242046440,394733904,229628931,972863639,560352685,565748682,161854715,344087899,883120564,624452797,109100058,303494388,865744482,454383265,342711840,730970359,539823601,563804146,615858969,822827942,915265523,849336713,88621940,31532768,987541283,171287447,3080599,193620090,853113794,668603547,875738447,194224419,484305895,501172607,797122849,467406010,209662179,209628035,378333294,891915978,467985375,529059786,7583672,892204939,373563582,282688177,1230097,823826425,151903333,521677553,362197017,1312853,617524658,180561302,579742962,844687030,466141571,458507756,752227186,494166357,32289046,630621795,290211450,645848179,991294099,479684461,54663329,824986316,434818098,659503415,603774328,702288279,848034126,162691455,906218178,96312623,16762046,431547631,529389515,740401700,145540302,403515590,990406927,798450897,715664604,313312425,68602847,452750689,407100842,64013926,714643262,153222592,765639405,632107012,524661964,383168294,959348167,169112240,688924834,179875437,143148840,862136337,369001665,437474300,962093605,508682365,202627958,348865258,733901709,751028244,950215094,362717178,419245712,900180610,929146574,829730285,831994543,915766354,842170858,892337704,804000703,131262263,106460288,504140225,669821681,559980598,708503798,24122435,708435412,932437160,227304569,233346401,93907684,327882732,216857298,927822547,191368046,148635614,862680176,353728656,398900009,208472467,255711708,6077867,469246567,976035785,848422458,921555637,62172437,171416373,291265035,882559426,10679310,931606382,474735218,167313981,734870548,668775488,307855261,590763115,781315006,852539042,168525107,466374767,592438484,366674019,191004816,776551856,354478943,631772713,329014890,281250489,146525874,525149329,858130188,625076876,83561354,6690569,166694177,342714606,484095335,98993950,671024030,553618888,513105433,233179579,270275172,843508563,138294292,370431481,539294476,247542580,562804367,381842649,54440288,112765213,294516328,820475581,33399298,983315762,83160388,908021223,99170605,489508368,899212397,305588113,928685309,375285952,764443029,513349442,866157244,490465197,600544429,204529603,59921812,670624718,851067673,745619862,346143802,283608633,700319516,52590249,538329536,242088842,131997103,295531309,206837065,861959108,339128339,898595411,553916122,258653256,355789776,661662689,698181215,554578556,1822185,374527272,999337005,603831918,979314115,641746467,568084582,134900089,637766786,974364206,831325232,625197901,547765250,482524711,14152406,443281398,22882334,998412406,756874303,799203041,84673202,212696302,570676788,983596440,832460482,839332884,948695653,70083947,180677902,678997803,231401359,35810546,129891818,186111335,28147537,519134453,988956780,323798346,679756615,479444800,424109441,296331122,987713027,809008891,135512515,501166183,433265881,657527237,717102470,903294594,774081939,787279467,871351260,620053943,473350806,210682512,131613588,44276696,595064265,721459676,951510177,649388088,55299753,896592094,385414342,668549708,472069537,656430623,868676201,266474082,36443784,61576757,615563320,19818413,581078515,380740534,140895585,172440184,173353898,103876343,802168051,227639199,392126031,606965951,434375822,85333095,847385710,893527915,530866218,441425991,285958908,203570177,969012759,336311596,752691592,859334994,36704593,898990128,44522709,743260848,393325671,331279281,431479422,521315133,708854638,633083212,841280347,241754471,973741306,535487163,51181337,904319872,682760074,92010484,199779114,252765768,742641902,817703738,267130742,201876435,961740720,166525321,189770305,914710889,703084933,605808476,953111417,592380999,119963636,914622401,385896251,521292510,946600899,476457679,600617105,329207746,229082696,689295557,539489354,66266501,637545082,818776971,525639481,582933669,908319865,100077988,912761999,182527720,70987043,47231281,547182057,609810441,840692677,711311637,228016089,870395369,593195667,592310138,815878691,159113253,383215741,860785055,744486637,96063944,13420353,635479792,201126189,877067114,329689816,666090464,743423835,684554936,270811057,238341152,255707353,391020641,856666451,709645092,550982065,936436748,934254424,637413645,677260174,62753212,118663169,205281121,999052639,550287172,756684465,762647219,760688904,350951790,719833177,971466381,275808657,674402162,694271735,518145599,467675282,121313426,211287647,358117895,516675286,411558682,459327979,182285622,693497305,961583799,556924682,20015314,13122803,652285939,868718053,967034396,812354885,111760450,900796791,93776205,29824710,198545144,811334777,673663625,680604372,889046730,608236878,687938619,39611460,835529480,442871723,778022877,481320995,887360733,629742160,863639990,325235713,532828771,210950403,391985209,924613992,707962312,259018795,714443434,164927178,123470442,564709880,685672558,743046637,369160218,100085870,363143201,434285145,486906284,769138208,317022092,460007255,212844585,65985262,347263211,459851651,62575598,430367553,380933830,467690950,848815005,925704232,697221779,229222892,338801721,293544418,978417992,778483957,799365258,955768921,406822136,744307713,151033781,115312330,100702648,376586626,138647356,362978843,887592983,935816094,710229810,226952291,208975425,2227518,50503548,965744643,681025125,6547220,242747179,829330321,927144499,279671651,302704331,69814303,883614539,112830051,518750778,967266962,813953586,12643437,689596064,385004978,140320815,204881401,976555226,222256792,204157533,163028234,162407559,788260771,661558597,202697065,41185699,338241329,344943160,172052045,172989451,110100245,151589042,807714099,536352452,570945589,113035446,711604127,156795321,900749915,247983133,171445580,9502931,851963490,482081746,106359861,407933683,290530869,51458424,732891654,809016067,11909477,507067123,941689806,888292599,645520668,87173179,644802690,539740202,463137495,613731411,884287040,71781033,325589433,775464411,80250942,672790567,274695579,985515376,296235267,285044668,237082940,977741383,777485425,170884032,470952138,726777004,168976527,783119915,876839635,170012973,438620113,96069563,337669306,757984144,791988947,205854600,323472839,783280775,156133680,334773241,431493181,938020139,722738468,295304611,400400649,742455810,840824425,874767680,436489832,891743986,648249050,178780908,355249425,893624929,660464856,472010522,728910816,396320847,343024342,916360565,339427745,843031314,577939183,512106376,851332751,948862163,742790482,454247836,818346277,875483722,106745897,24331400,210607206,819124547,693994138,418429197,890923425,283869834,49705628,823161955,982725127,431766196,18316649,691972387,288487063,579534673,198845610,476071592,672235935,717416100,837521211,375477816,959030499,232950052,536725822,181761797,951714582,837036968,249911790,204618728,411761236,361564540,362574854,463817715,236599257,960353253,252915912,994117121,149327006,493089516,12319206,614918740,39756136,844215160,478154932,928366143,984274483,857007579,60421539,768185863,549934787,556328924,224253486,329634080,942136600,558648910,527193012,766549278,164688678,713858082,231811119,625692587,839763348,763995068,175789285,879537352,945721109,375307201,666982421,156023006,959521481,778979562,311728071,305949335,92529510,494896475,757940373,31380082,53898110,602170744,817784751,459312608,611524941,991064255,68493189,234080232,433356488,33989337,254355086,203416298,670539711,984909379,942751991,214459147,742381392,406517401,659538798,545791280,311630973,710664884,250889498,323700484,731319314,442656371,426954184,456147866,959648662,992530446,349089169,702550810,875846003,222573123,490092230,315546110,820510217,23746040,920266474,834234827,489720642,872212004,878505528,80648158,868208618,636742288,407150331,907283197,337554998,306048934,578449777,159652270,393912976,426590380,221668256,173801016,658762756,261172241,102203034,457484024,448296964,585420188,740629543,89855757,945574111,353235144,410740496,174446149,282526128,287384888,461186569,230676516,391162638,451927456,829006140,645807553,913440276,412282670,973694951,396248766,67701610,840325715,286254140,558438793,913765863,2894375,64680394,269835476,735630346,939878952,7424821,324197200,905194189,568127894,199424785,879473805,905711957,741936546,992215678,185611270,398289119,831837529,967145376,117866072,764502506,230854893,903148529,331294152,56194475,671013546,740715820,400758906,132200135,173292177,940540509,160126594,295139228,124038822,144710761,985354733,544860589,911943898,345067070,206242479,445926828,125113776,820009107,742130244,918949564,903757898,256019420,769874313,936977089,492463358,678650620,627342020,112966905,623972483,77486386,979252720,390842133,437695387,80219559,220410840,632080322,532659855,625935328,496539847,116981109,200731184,70163172,621472312,199378605,432312000,891576811,334596732,918033910,209095549,230556275,302525313,247569443,958141180,307048862,390199018,469801104,298036703,832784353,610368806,625424971,837821395,334609312,756054075,894696222,738910118,693488468,750168392,153939469,869320052,844054427,118067355,688667856,666175026,211728472,158093405,863823884,227400624,432309833,232650649,720937918,921442020,928735687,103605794,601085237,154776706,547911408,386614805,685161562}; int main() { /*freopen("ans.txt","w",stdout); for(n=954;n<=1000;n++) { memset(f,-1,sizeof(f)); printf("%d,",getans(n)); }*/ cin>>n; cout<<ans[n-1]<<endl; return 0; }