找到第n个加泰罗尼亚数字mod m的最快（已知）算法是什么？

Z时代
2024-01-10
分类：问答

问题是要找到数模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)，这太慢了

所以我想知道还有没有其他更快的算法可以找到我不知道的数字？

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];
}

回答：

十分简单。计算二项式系数的素因子。使用筛子的简单任务。我不会继续介绍它，但是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个加泰罗尼亚数字mod m的最快（已知）算法是什么？的全部内容，来源链接： utcz.com/qa/411101.html