hdu6680

hdu6680 Rikka with Quicksort
传送门
题意
给出函数

[left{ egin{matrix} g_m(i)=0,0leq ileq m\ g_m(i)=i-1+frac{1}{i}sum_{j=1}^{i}(g_m(j-1)+g_m(i-j)),i>m end{matrix} ight. ]

以及(n,m(1leq mleq nleq 1e9))的值，计算(g_m(n) mod (1e9+7))
题解
设(a_n=g_m(i),S_n=sum_{i=1}^{n}a_n)
当(n>m)时，由于(sum_{j=1}^{i}(g_m(j-1)+g_m(i-j))=2*sum_{j=1}^{i}g_m(j-1)=2S_{n-1})
所以(a_n=n-1+frac{2}{n}S_{n-1})
所以(S_n=S_{n-1}+a_n=S_{n-1}+n-1+frac{2}{n}S_{n-1}=n-1+frac{n+2}{n}S_{n-1})
两边同时除以((n+1)(n+2))，得到
(frac{S_n}{(n+1)(n+2)}=frac{(n-1)}{(n+1)(n+2)}+frac{S_{n-1}}{n(n+1)})
设(f_n=frac{S_n}{(n+1)(n+2)})
则(f_n=frac{(n-1)}{(n+1)(n+2)}+f_{n-1})
分段打表计算(f_n)的值，也就是(frac{(n-1)}{(n+1)(n+2)})的前缀和，就可以得到(S_n)的值，进而得到(a_n)的值
打表代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;

const int mod=1e9+7;

LL qp(LL a,LL b){
    LL ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main(){
    LL x=0;
    freopen("data.out","w",stdout);
    printf("0,");
    for(int i=1;i<=1e9;i++){
        x=(x+1ll*(i-1)*qp(i+1,mod-2)%mod*qp(i+2,mod-2)%mod)%mod;
        if(i%500000==0) printf("%lld,",x); 
    }
}

题目代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<sstream>
#include<cmath>
#include<ctime>
#include<climits>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define PLI pair<LL,int>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;

const int lens=500000;
const int mod=1e9+7;
int table[]={0,367631060,416495341,312866495,864422505,839083452,12274495,296922560,165736797,178687671,45513528,959617059,907969740,209690930,998842553,465169763,265853810,657766420,234752773,689334482,211535148,220532609,218147054,534793035,977778800,59125624,155307713,5109642,504218398,558032090,355562371,78281979,657514755,136221681,734214987,135048532,698555650,874131761,428951372,907140402,249033323,342474578,285148375,953181098,274605739,448568388,338808663,476020936,994414699,853282425,608885782,960456812,56743518,588202804,402157044,662478809,832425005,9066205,829118770,928753244,354377916,318976895,435655567,410301260,159046301,137135076,162937071,928999173,184431844,312900794,756250834,889234789,200861698,996606186,901660772,510861323,972009731,293148505,869619483,424395325,927422185,95462189,135734976,418685792,435907069,124095618,741119707,751342140,489957190,912092561,906042258,12909523,791698432,732306601,306799763,120648379,508431604,494594060,108542774,129661807,240263064,897535368,576987022,317917754,485649473,785051077,680622326,377595485,717071900,937381849,624151210,119953887,983811862,586679874,707663439,436611606,521406514,502310459,975029971,504025836,587205928,410828125,608133297,421860420,296993162,867622445,721500554,655855168,993238219,914118475,51262505,589135201,71578037,247240521,360906467,594945904,184731867,805760293,833028231,910357398,82224834,975660951,268408365,847449717,146356515,562620479,929728098,852004855,206473409,946394676,863220082,649322791,280428957,357678382,226748229,807653212,877487170,778693149,994174733,945894295,27648222,931682819,808783571,635791874,74852114,550341803,775821876,921901579,135151256,377664017,927497455,398306653,765008343,959715351,887165205,108229174,519437663,885845356,957846611,630517004,528227783,231078471,414230982,53219084,666735328,768839578,597180915,609184788,42744559,914722723,380932379,271768052,348308161,320228531,492753477,393150554,583552826,684709488,53005468,972949808,846505392,286515437,685010707,276211775,383307622,177895317,56790451,743152811,684014983,435380032,340540340,129698818,621001948,170167081,816303098,871518425,29935919,88492245,73162324,438852764,967960859,855761802,46102073,42991241,899095549,839358117,991028554,648713407,346421501,199916211,502873189,37986776,478280026,924420678,600984357,973132888,49449177,287659969,659480720,260894110,313954869,419149432,302216867,66645682,651621754,232509196,545261467,81151904,451666784,782505112,229887728,214742552,245148458,18460011,429220589,139166348,590531119,613272257,10415563,304031038,444303571,262544284,911668327,640533692,967438882,146157642,221166498,829502868,988472937,895958477,964954742,338299229,27762076,666901962,149734779,362469232,436593785,386731988,703357790,912029883,337793070,733783956,149070049,939179123,679839510,363577837,898569029,993896698,202666767,272165631,452686251,138797446,304533025,706767770,767505123,952259,452091527,11340134,114178294,620211698,148360414,716571312,349961983,878845019,110161307,195945016,425800918,741838235,106197609,468505032,745421655,20250220,493665953,945442925,599523469,826563319,225245427,185933861,125639917,717863354,37662220,475418818,727733521,771976318,832022217,404474696,208826213,604554531,347457723,623443580,238266927,678344632,955556994,468612166,462747556,181675575,849791429,469852509,764669391,765683456,79342097,136333814,946379206,495902542,546738897,81505766,990009683,740540153,663448222,29667239,415050990,481056440,527292495,378128657,728965062,355597416,809000210,128828520,491444733,25750245,183240845,271664677,742940734,428414536,741430771,418660210,936440362,571765458,811725513,788838977,392931391,19972942,921412895,641651192,908855177,845621407,648040522,455865701,434985504,814436488,866273132,28707773,343962733,579164592,910126292,270486870,748987208,209942708,27314353,879315022,797193258,514725618,857990177,361146875,101839528,248136117,21009799,897910726,484861129,355365178,197002259,238249723,967332432,855955538,828415100,28076346,60587384,998147119,929088576,143865921,987862713,789262846,622523197,135739915,68174041,954901038,673037844,157597580,510231805,994799035,402518746,228762260,718111142,190649946,803764385,838039622,626464450,690972145,783940885,146672980,241697627,959447338,655763355,725979146,249686601,626978673,27013634,422431380,993052378,575245965,677676661,948222281,654806062,138423121,345342759,103514144,76560912,580930991,336846243,909143152,504900833,481809591,467599291,889664741,486363126,480059505,505674937,22863933,810478974,851051661,486169036,832071674,435995126,757795262,206065693,627859082,754579310,747999769,424932027,240647901,821057065,439600200,16841983,234322750,467416458,635442586,224639808,915834445,496500261,173760431,396386378,195566946,843391857,63135224,185023592,564880916,868735536,239904773,59443498,744970071,415214776,876787630,713878227,3548881,80081937,343419524,941921899,642244898,907875236,73993879,30474449,488260188,541625898,134531127,18555543,935586923,866529789,329571386,946449209,225657357,313289176,268875669,704037713,206325156,993464992,545045674,992142239,488334594,385907738,282485797,195754071,426001600,574095062,622785805,928001586,167198,200828805,48042310,569901214,306002386,923020893,744000884,235592387,596314300,417786774,913607475,646965910,889519087,300527691,460270155,598277451,528998152,903719769,158954433,400360200,192617510,176330189,704725994,977995940,241107792,900731769,928034230,765393155,636090197,834428885,309080997,960491115,627059614,371053449,387267837,369600855,413884868,821419066,392681073,181951446,533003607,836645477,926000450,327943908,805939155,225497109,608749449,217873149,188022022,798982491,78923028,690639229,428901205,668444088,259885124,416732765,217046194,360907121,17674850,404657053,504213326,857855358,30246705,907376164,305623913,882165967,412105896,565705803,107278705,880420249,413858671,462249231,999395472,365594257,435874449,856380759,823549972,686010347,829142400,93299085,149954593,267861840,348296723,250359250,678216041,134511915,886438446,258258190,464631952,528547327,101844184,496780158,888574683,97068043,316579676,327328903,877506141,796896389,258606768,856959992,816843732,160624176,198441531,13162534,308076271,58998984,411457456,537838870,80690691,141201203,357896264,864827061,869486989,72773576,922334408,884552674,92179962,902066633,808005352,290147569,570550185,406891331,49964156,834581901,321591489,751394100,461716814,866706973,983938110,493213426,703915772,196449911,165303852,392833791,967785586,372048175,913098445,385557741,41189814,296868137,273170750,262047493,583900,814838044,735308342,817121161,213807188,388092904,360302052,425723697,778845154,61152056,717471515,344963122,713981802,310770590,179345174,166700291,578918322,32046135,423652711,348002400,745717220,159074417,792465087,76001329,749880484,370825730,163198071,729425617,166628933,817307299,779287037,480183886,895013004,613957195,959233684,215332041,11500307,406858885,208378494,581842088,46184539,654396202,153143295,243822516,892726733,456271527,603280914,115987925,457069973,201326849,190158567,704197848,459416379,376475963,424315232,50481422,778135378,176824048,111127104,347877558,956945085,494413110,491149149,458075614,418242318,240216718,325145304,116953132,258467131,393907014,374448105,26309771,839923154,328100674,870818065,358478362,50100645,850119988,616855336,719122543,25070608,284509118,515336985,118044115,13864026,755121031,50766451,9591961,255003348,900745565,157061255,746462772,387677480,956291955,994000203,154297905,563460296,618625545,248074442,875395390,547761836,24065033,383891165,784512103,54422306,245339529,649360545,950312920,295682540,476541450,902916248,444885323,161900135,243499504,462094329,286605520,734747963,122936675,122897779,418115012,43173018,155537681,457794287,887376444,451677935,489942561,582582252,262241368,292329925,32940126,659169751,256018275,412294818,16533364,698219573,769740953,526651745,34278243,572436423,797440365,376598572,386343218,956079492,495922329,931506761,95888947,904003200,717775706,867720538,488424521,217196050,957285374,518967734,477781406,125390372,182030165,29145964,199326026,52109641,317953786,395714630,797523980,278444669,704849983,808661584,659412184,914983305,933083468,986914808,935596739,594221633,591885438,238733077,816703021,11475646,407577363,879755940,392846069,473504354,530778971,114598423,814306836,539304115,488035574,829828434,527111693,730928047,871789017,179394183,671576260,905638502,395567982,178157359,665233199,149507922,421600713,761022104,971876411,240951807,92790105,813928383,571732912,83227863,736688884,718265831,787385469,876124354,311914217,202796102,144039909,907348322,711654018,41711032,60179451,257578225,667707551,351814799,392142918,571992140,453951422,71013578,433379379,84849046,150258716,857895793,520513498,978150578,704000206,977038065,9501527,959539836,773292246,742742207,117636819,625666208,325795686,81819585,35560036,773578817,960413034,918683748,655231228,228636082,734661983,525369423,753084894,828556963,805992947,351679493,688232255,776133719,797096827,173500995,169116553,263137800,936151086,242945239,186694260,701929696,972318087,328756978,988625917,532363824,974040511,977566161,161162403,244209154,647145485,33493746,478757143,753634838,604681466,98489532,370355616,3124232,855342148,300354953,577680835,958270875,647761214,839111719,75842155,972469053,527208096,638937259,94157560,571522237,349401358,149560122,716947545,14816691,768139322,291728547,719327102,646219780,656532108,847844821,781751022,826375350,551653718,247466509,683985780,480496725,820795864,158115345,56864274,511171776,813090398,161786048,242653988,806619515,898710629,11594049,561286260,305351145,860903714,879175016,358954947,914231845,45391892,145501286,956358581,335413536,971884604,982877360,24026430,406939109,627961412,852825055,489382745,26830952,472454659,227417280,186982959,944412956,641057174,54707850,3429505,67501109,102972380,810205275,530397550,459888806,429000182,829186424,80086169,502843885,690251818,431178888,177920599,866625505,723704760,970519058,266651281,977652770,485318105,663917420,150698687,509152287,967754496,242834007,709592864,398177013,745997503,924212758,583712235,853436605,433022142,846889591,553384376,223313302,776090649,716215286,900749468,774315657,835563214,275751649,709754178,200108504,422679695,53747298,433047385,326863150,791105510,121892685,819058654,592140752,496493936,429247279,921823631,814684003,802569306,896406682,993036578,267518107,815952279,557067462,676225788,269658194,748725309,960850842,193379366,46691407,495814369,831091846,917437299,675400258,556350645,26377701,375952770,530320213,984502648,447147692,436886849,647951073,514898236,401097736,94493256,346141911,90106929,591578794,943680838,587679711,658569976,334986678,151559091,570164256,566119441,646188623,413717532,850963097,574808848,936025926,210146204,751845276,540672891,369503335,507683361,660175545,943351157,19244052,285171125,925322168,390914238,11322882,977946598,723349895,991441525,14061891,970840666,729453049,600258014,950368548,515292165,495167173,110487493,221054355,545775687,834548148,759608332,364808147,552997318,56552965,566219778,80144008,662179047,768070579,460391429,602218623,918145881,640403805,896669452,449715971,922971942,378254479,439454302,187386207,817446823,33388289,783006350,540423125,217034153,864847842,388853256,41450978,335270569,764397448,742258241,666325716,453493821,180765341,581884114,199320668,457536900,63827505,487234870,342478211,703039876,933845533,533339601,134059946,161329116,684742746,880893256,889195644,771492049,205504302,122525643,157505348,20028966,449799481,142439894,921113084,244870463,954247482,276027945,446899201,118166587,59220220,903022834,765333936,593229838,552736242,68188188,698749811,437708859,444146761,471204977,750894664,632470439,633324632,417291492,803309283,168048524,739603593,679497446,529155096,574110201,822508695,76154184,743615441,522999247,937404209,151805270,255276219,833287857,971821426,173292556,84239980,181533796,452647561,877008536,1017974,455355284,413345300,568367282,383996953,109341373,951101208,421086494,960605128,836570111,545306843,324467158,112068213,781098666,809408527,883162393,566173275,769043159,792784383,481035782,11270791,939479001,942898028,476219898,420279420,561475190,175981201,363576979,566131217,73213601,612009706,203849544,165259690,691701965,752996728,881346240,730145075,218391685,93293452,217175385,566637470,498627218,27467423,471425801,607514518,208575389,89405729,390498738,476029887,92645550,619321649,999313551,664249999,23752354,649060197,470011911,115066385,642913355,430476187,928239001,528880077,466851084,371206087,806508537,248552924,331836205,930612223,99646847,303635564,585526269,450993938,473896250,564808433,939524733,416326982,14567458,937707842,332170930,515611038,574783214,737071366,630134151,626684438,580794823,41288769,293439121,535983815,369440165,615288389,394440896,123011408,118819165,878558378,315018821,179757556,565620953,648918490,249406817,73341627,834081565,902627868,640727227,228119562,877503539,258839704,664470910,762846179,843246240,517817751,902541296,105261759,670996757,952291865,972058439,51894511,32064642,818432236,966578203,612639494,498462174,29795989,710984562,733239559,632912980,898407271,168483667,613859872,577599637,21480288,208659669,632483368,5227987,420046598,400902540,824935057,755929364,154724167,818296547,213091347,559391719,670747275,293383551,400430553,603103761,773410547,358916546,255332521,165204310,258991714,275528682,758681052,418971562,510905690,220871088,485355755,202322377,771868795,172417427,569112961,201477755,462350640,598116468,549350782,236401392,932807150,324866420,193158456,229458914,105647498,18000934,806201212,575911027,541439096,206432713,196042533,512195510,817579011,34091833,61865876,372223852,893616172,374025463,131958459,810874768,105806574,349131958,721988555,28993999,827282997,275064421,350537117,883779249,433522596,540813309,673278188,550373058,480321655,10135013,853019695,348672108,178850670,744194836,254877131,694886864,94942859,332678387,270665646,875104419,720123228,871144191,595160754,599742223,451843726,159622049,708433842,479000011,879703005,157439021,569919562,497404852,807493848,426836656,340514857,461755907,537379218,52439006,116901770,46032175,683767505,3116917,365799897,527203595,844231059,253420470,247780764,688525283,541778284,589643470,584346763,135177460,479531299,797770426,106910975,191161599,238648045,484205379,390328610,147462265,80845838,755121732,415348822,350954664,260693706,208182117,150049272,697186034,790892169,358422042,304173600,21991191,354580817,532272310,786539700,650517134,327866580,832033094,876479074,185041486,377263352,429275074,758280320,926412295,605373457,626220710,632575817,807996795,926948037,685700223,881315291,156896108,537198089,844149661,318979352,14027100,632224434,263945771,853157943,906559847,262666411,944318457,818088747,234384821,218688313,152740901,97953872,21141353,459440587,51844983,42107255,277497997,628585939,397126008,932422337,886356967,420678206,335723903,351032465,848614979,552945351,803663745,820687594,980682860,687034052,823791272,561782293,290572118,296137267,176989829,947104704,611040452,499499234,107865603,772242660,14995929,111826496,188659265,693705964,427625833,262826995,576560978,226531774,758319842,172915615,687723639,7838170,800557524,611372950,842894838,246849793,929248982,891087536,430770027,830621492,396906341,335344517,183188683,233826816,382041323,578349125,612062168,473899641,572932599,983589332,36926133,313497551,119227170,804172391,169067462,5298974,543249481,50784182,423504317,13973713,208761441,993427632,738661683,896918534,299656786,817262507,67615522,375784303,51495046,535059784,891389020,659479020,190282030,918659875,435808243,539430604,543162161,636642133,702344140,607541118,545129197,82184410,585674527,637010029,584155250,31259359,252979653,330276140,219984121,961914859,799591551,503970645,615721648,287609736,333221125,287249350,594890278,608346916,804960918,598306898,382914836,703484850,124357458,288191896,158576280,166692755,200696683,239090197,784427709,344692177,77939121,902966769,505863700,261226246,394782589,761567779,372897653,583168050,830454180,279591365,795647523,214146310,473955184,404798867,85321830,515598774,699872308,10945342,315590580,394445105,835043338,59235944,252425923,117322526,34051620,278591764,727830902,86841763,623273441,912807902,418248460,760193802,370144654,260593248,786400703,764255212,142983398,227250026,585693765,586471396,175849205,427204948,686772959,793361853,932467799,240884242,208239873,359148725,634660113,969142672,632494065,702552678,407805857,326346111,354908864,278712333,782069256,404514302,207330417,221811229,434087202,913092879,562881334,877748897,273680469,760533451,1476007,171730544,107228627,975882541,443539006,657661077,742391670,34349682,336339512,995192994,451335529,864713888,130106184,922580386,115197012,472746078,656999381,861938045,937959675,884043437,939114314,159881188,222736780,337301102,716955114,30451046,6887981,215445933,284819515,646516324,485374446,356343817,689826325,499977846,765154676,173478866,929022030,92956403,383481804,201553556,722470696,995644583,970735768,736291062,555952434,123762499,205652849,426681963,115406183,84815967,692828674,619447218,485336332,908345900,224849709,549852185,205074064,869842842,818163427,679836965,278094956,352020254,864302696,29534418,988373066,857676755,108812807,192695878,764026945,228034105,28931487,113241064,940344278,591191063,98571231,353741806,494604648,598254280,429870287,208594548,701397095,824119287,57112750,762314539,656136957,723394828,321068604,994965506,511541509,19472615,11528419,60956427,219395758,766023810,92263051,160630725,13661294,200759507,607704378,293181544,737017446,210945278,647849310,955105061,714494182,328480292,609734543,430667049,639086166,723028817,378031344,449213625,740970020,346797118,450969940,870448946,630781791,598452123,371809157,14986711,253211514,222752455,816538087,79944043,493428287,28950836,145165113,389549479,80792511,683446993,142976596,635699414,755293812,192825423,346519201,746766735,319382985,571871485,617875864,245065261,496481086,233519838,100040858,506806302,400107466,903602162,637748994,699581100,468699525,146079631,99634520,370764786,966336005,944874794,953490990,312862274,434601721,378609456,333011689,910681250,559846301,626185224,874782636,948410650,753960885,779662166,686163748,591970524,179504813,715359226,245424024,650902976,335599952,597274496,382981253,951654236,256037618,468961472,404095953,383542152,589378271,529203031,865192188,491877495,684198593,280070987,944726828,769989269,868345122,363266849,36318272,82611264,652793445,331168734,761840598,728302738,594283679,985880030,892385075,670069766,726505952,989404323,295328934,467594587,369938893,216940118,689931874,677149517,11589397,162083979,786051532,468532238,24795698,312967478,513093994,541725392,251073938,438207102,72288304,764498001,421875936,877100538,919945053,713910916,342116348,934376371,206391445,523404828,236378337,132316023,756306808,601205847,909130510,465369427,8869718,838377183,88217792,156071642,206676817,167495408,546837483,812170465,492847403,821731704,576154202,813956348,644104457,707193,529489672,809234147,679731656,230990968,731194065,226823190,392646422,372139925,681306445,941686624,511904564,215846088,54186796,974801918,489482566,98982625,393178217,616517733,245921995,969795820,790485595,19309225,256151540,135974600,661122182,868266,149833465,421758533,39204599,288932677,176665131,264162972,292634998,389552917,359176597,191867792,56877706,293459671,492435644,855311521,899501973,895433393,552970302,323768233,223540988,768331790,377903138,663043497,184324864,116336592,163648402,955518127,7539992,976513088,783333338};

LL qp(LL a,LL b){
    LL ans=1;
    while(b){
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

LL sum(int n){
    int m=n/lens;
    LL ans=table[m];
    for(int i=n/lens*lens+1;i<=n;i++){
        ans=(ans+1ll*(i-1)*qp(i+1,mod-2)%mod*qp(i+2,mod-2)%mod)%mod;
    }
    return ans;
}

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d %d",&n,&m);
        n--;
        LL ans=(sum(n)-sum(m)+mod)%mod;
        ans=ans*(n+1)%mod*(n+2)%mod;
        n++;
        printf("%lld
",((n-1+mod)%mod+2ll*qp(n,mod-2)%mod*ans%mod)%mod);
    }
}