大佬教程收集整理的这篇文章主要介绍了找到第n个加泰罗尼亚数字mod m的最快（已知）算法是什么？，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
十分简单。计算二项式系数的素因子。使用筛子的简单任务。我不会继续介绍它，但是powermod计算是微不足道的，您甚至不需要除法。
对于N = 10000，我很快就得到了42224403014400。
但是，如果您想要完整的数字本身，那么第10000个加泰罗尼亚语数字本身就是…
22453781249338521563359358425736057870110358621936588777329371383585
443658870053449099810271911432021020990539379958970114932732650095370271
397751300183876130693653440780258549445459994177372998459176454278220288
679699783327649549651476024591222065426709156831181207130089121989402216
517545144106669143509197596949973192167548893412063804651413496597406903
967719298471463870452875276986356795262033484770727452974197655810423629
386184662262278329466750526865120502476640878488187299740404235631962632
335108916990663560351330901464515744357084282208286669901241545533951877
777078174205283779947690623035078595904048715811899275348402286537327410
009576296851062523691528014340846065120667839872568170381150542379156626
173532955062796771718993285598391346886779480658586379448386923993317934
139425945651509102645665277040984870211604644540699508509248821099873225
565699224344151993874742555422872473424262356666363196825449089721410665
537521519676271082500130505509387186351879731113568837096419481746389018
721284533242225719341420124434480886444987373634542567071582458263380247
628252179873943804465262216365735901268165347321451279736504798992232739
106390706179212626442096326217616178171108663008963682821183764312867791
507672494716865305031842633900748973827504534625795968537648004286087039
823233370550650634239448544304798764239028734674653967478032618882557954
859328131980782727940394400855369003385513208814011609977239377877068501
893633819436630205358663340684840462204867552576509569736390978718963517
869423927523718504671005747648411794527978689778762460237949479732242725
154275831263823307362585789708343583184171797113785187466609433767144371
710845773715328364171910363978492352051901370003068055356444233141131383
192077598317531370925033378421138581148001529316546340657631162629562941
211065221871760353772365014435796695284269667873562415761642871681276498
507492541421942131281008978510862112693424595990036710403533420006771490
575482785612280198742983770649313043583275207213939274300662039637048647
395250014477941359641726047221826652916778311801541491816826072282488555
018173563867058868251361080516013361134986419403377613243853586312008767
909635869692823359899687030213634793656744420820912530014968355236934193
747181786083577435923400955703014812335311495073521773651461701750485101
119310472898683618090898735223665962918372501660743711042258315604294195
583076309209507444333462531858856911411408798540404888967120239682480627
570158137868956844950713279360385273144560292399045892610118082102910880
862332337854786916935223744892537176357434650161037841572213751901947447
479406915511862629144757855890852243043614898752155191154178797427659170
858428903659564218086017881546286273599385917718058276038925354040884258
022546721698832195059172836919416429064599278227491956109630837263590884
232587058023101145921693423507849076470763334833613166731358258440439729
023251976962577737416518794914009277934381234511794730677137605309953636
716963188964230436087118746073758080815722286112796870306754227017546055
347853334923811143440952672436342961180384459596879312187164969968096364
679341577416027452001090523659332406246454292701122715894579618818643071
139925009651888661718404932582731927646801878919152052218535889565319288
284306134970608577076704660104569794464663831193002735423564364371354521
236158069405955372080665906666149641642367693009585743888230289135078928
729184475260174446278915850624301208853693618442212023236924456444468934
014289741543223145235333811594418344798647068944904371005158995839127368
111629241573877617157577569590584624720552246920280151741755137476154967
741272080362312952750328628775530857638646138592895858764915987201920286
661490154786097488396300779244279606416541720716707237058679072236693234
932525387774462125138686406910133757255779021404876020200833761157767584
015369673586027681003369474431448843539054790848335705489738731700240579
310855452462903455809888697753847348175077261616431384533713924568807999
599683993362082982833949280082553659996487889394727840889035163412693106
865702752400579571351436509808650503057036278511515529330634352096987240
087618010503197530225589878764240330302768263496958673020211712107611762
945771002810537812467742009399047607169797035466100221770262334445478074
080845928677855301631860443068261061887109865290453732333638130446973519
286828584088203627113605849939106943614542645022903932947597417823646592
053417189520415596451505598330301782369213897762201629272201936584136036
027455748892667375417522206148332891409959866390232031014358337935412166
499617373308661369292739138448626161089231445046384163766705419698533262
040353901193260661841441922949263756492472641127072018961101915467728184
640938751407261817683231072132781927769994322689591991504965204544928105
747119997826784396172488376877215547707335474490892399544875233372674064
229287210750045834971802632275569822679385098328070604595140732389126327
092826465756212595551194678295464565601548041854366455751504169209131794
100099734293551231149329072243438440125013340293416345726479426178738686
238273833019523777019099811511419301476900607138083408535229058593795242
998150989330379630607152057165593682028276808657989133687600036850256257
973833780907105126134335912174477305526445570101413725539992976023375381
201759604514592679113676113078381084050224814280307372001545194100603017
219283437543128615425515965977881708976796492254901456997277712672653778
789696887633779923567912536882486775488103616173080561347127863398147885
811314120272830343521897029277536628882920301387371334992369039412492040
272569854478601604868543152581104741474604522753521632753090182704058850
525546680379379188800223157168606861776429258407513523623704438333489387
460217759660297923471793682082742722961582765796049294605969530190679149
426065241142453853283673009798518752237906836442958353267589634936329512
043142900668824981800672231156890228835045258196841806861681826866706774
199447245550164975361170844597908233890221446745462710788815648943858461
7793175431865532382711812960546611287516640
问题是要找到 第n个加泰罗尼亚 数模m，其中m是 不是素数 ，m = (10^14 + 7)。这是我尝试过的方法列表：（max
N = 10,000）
ncr(2*n,n)/(n + 1)，再次是不够快，由于ncr功能，不能使用加速 幂平方 ，因为m不是素数。Catalans，但由于文件大小限制而失败。C(i,k) = C(i-1,k-1) + C(i-1,k)，这太慢了所以我想知道还有没有其他更快的算法可以找到我不知道的 第n个加泰罗尼亚 数字？
使用动态编程
void generate_catalan_numbers() {
catalan[1] = 1;
for (int i = 2; i <= MAX_NUMBERS; i++) {
for (int j = 1; j <= i - 1; j++) {
catalan[i] = (catalan[i] + ((catalan[j]) * catalan[i - j]) % MODULO) % MODULO;
}
catalan[i] = catalan[i] % MODULO;
}
}
使用原始公式
ull n_choose_r(ull n,ull r) {
if (n < r)
return 0;
if (r > n/2) {
r = n - r;
}
ull result = 1;
ull common_divisor;
for (int i = 1; i <= r; ++i) {
common_divisor = gcd(result,i);
result /= common_divisor;
result *= (n - i + 1) / (i / common_divisor);
}
return result;
}
使用递归关系
ull n_choose_r_relation(ull n,ull r) {
for (int i = 0; i <= n + 1; ++i) {
for (int k = 0; k <= r && k <= i; ++k) {
if (k == 0 || k == i) {
ncr[i][k] = 1;
}
else {
ncr[i][k] = (ncr[i - 1][k - 1] + ncr[i - 1][k]) % MODULO;
}
}
}
return ncr[n][r];
}
以上是大佬教程为你收集整理的找到第n个加泰罗尼亚数字mod m的最快（已知）算法是什么？全部内容，希望文章能够帮你解决找到第n个加泰罗尼亚数字mod m的最快（已知）算法是什么？所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。