题解：P9004 [RC-07] Abnormal Permutation Tuples

题意简述

给定

n, m, mod

，计算出有多少个由

1\sim n

的排列组成的有序

m

元组

(p_1,p_2,\dots,p_m)

满足字典序严格递增和逆序对严格递减。结果对

mod

取模。

你需要对于所有

1\le i\le n,1\le j\le m

的

(i,j)

求出答案。

思路

首先注意到每个排列可通过其逆序对数唯一标识，故找到一组字典序递增、逆序对数递减的排列序列，其本质上就是一个排列逆序对数与字典序的双单调关系计数问题。

考虑从小到大构造排列，逐个加入元素。每插入一个新数时，它可以放在已有序列中的任意位置，从而产生

0 \sim k-1

个新增逆序对。

我们设计一个三维的 DP 状态

f_{i,j,x}

表示选了

x

个排列时构造长度为

i,j

的合法结构数量。其中

i,j

表示二维“插入位置坐标”，

x

表示形成的元组长度，维度间通过前缀和优化保证严格的递增/递减约束。

接下来考虑如何转移。我们可以搞三个辅助数组：

$g$ ：当前插入后的搬移态；
$h$ ：计算二维前缀和，表示所有“可转移路径”的累计；
$t1$ ：临时卷积结果，用于融合上一层的转移量。

于是乎转移方式就很简单了：

将上一步 $f$ 状态复制到 $g$ ；
构造 $h$ 为 $g$ 的二维前缀和；
枚举三重下标 $(i,j,k)$ ，卷积叠加形成新状态 $t1$ ；
合并回 $f$ ，得到新的计数结果。

注意卷积只从下三角到上三角方向累加，才能保证严格性条件。

然后答案就很显然了：每次插入一个数，相当于长度

+1

的转移。总共需要执行

\frac{n(n-1)}{2}

次 step() 操作（详见代码）。

最终输出

f(i,j) = \sum_{a,b} f[a][b][j] \pmod{mod}

即可。时间复杂度为

O(n^8 \times m^2)

，理论上较高，但是实际上可过。

还有没有更简单的做法呢？

有的兄弟，有的！那就是——

打表！

注意到输入只有三个数

n, m, mod

，且

n, m

范围都很小，所以不难想到打表。（这也是本蒟蒻的赛时做法 qwq）

考虑使用高精度将所有

n, m

的取模前的答案存下来，然后再写一个高精度取模即可。

这里是一个高精度取模模板：

CPP

123456int gaojingduqumo(string s, int mod)
{
    ll res = 0;
    int len = s.length();
    for (int i = 0; i < len; i++) res = (res * 10 + (s[i] - '0')) % mod;
    return res;
}

具体怎么打的就不详细说了（~~因为我也忘了~~），反正我当时设了一个四维暴力 DP 状态，然后打了四个小时把表打完了。

打表的 AC Record。

打完之后效果如下：

CPP

12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include <bits/stdc++.h>
#define ll long long
using namespace std;

int gaojingduqumo(string s, int mod)
{
    ll res = 0;
    int len = s.length();
    for (int i = 0; i < len; i++)
    {
        res = (res * 10 + (s[i] - '0')) % mod;
    }
    return res;
}

string biao[15][30] = {
    {"1", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"2", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"6", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"24", "17", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"120", "904", "1226", "269", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"720", "45926", "800998", "4901181", "10971466", "8136726", "1449316", "18224", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"5040", "2725016", "469410230", "34289048384", "1199214348636", "21122470795210", "188578072071132", "826484526896686", "1645364274925798", "1281653971080473", "289841382414626", "9153271964330", "1536587906", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"40320", "196884712", "330125920310", "254288932308611", "103165728985389488", "23743839243991171025", "3230307420014952776828", "265026898195526421398629", "13166210770405964887226990", "392181961447581986411479398", "6838997133854163014179942888", "67073079314115247817527605765", "347999136404480418556467732330", "871401769548943630999162182454", "913606729767294025675147157548", "315488863155448757878131451828", "22086796125468253616041258790", "82070149293231029921353187", "55870226427283990810", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
    {"362880", "17350671831", "297712474287630", "2450983394791237021", "11150282314532423796268", "30407435063073870848529349", "52291047417019376038400979436", "58567014766883839972824292495314", "43584925711422649604287456605918086", "21788014038906372147098405464473439383", "7342949087594830657291604790316611984402", "1663804642262069375025219147345572166092943", "251252700911213495741967482983456689202739184", "24914448227611173706530947758494396207276239075", "1587929421095510214654556627983312587008868446532", "63198910716366522868752411732318603596156398801528", "1512309867224304683394656605829339115387365257352096", "20712162950423989275375200796534898746579575792227111", "152189943331977474656883563951889126599332497532610540", "549967659510945516147774636155931363902289618154856832", "864366997305553689184328371582698417333655518551805612", "489287505066945828601997160496993444779623580077295401", "71503323032206313949913341736908229246390978592986422", "1287182622006029776500365109846870385198912520391907", "334298460269369651901285550878239408033421413068", "327622448870742065114239240692172913782", "0", "0", "0", "0"},
    {"3628800", "1847029162807", "347401414834324686", "32223826474591876978110", "1700331273372456978013186156", "55527431330948218528676724954134", "1185120292573528249061443637916716636", "17153888209194071629284594401101939558889", "172762397630233772941765468441960259648193966", "1232310362242292448273724891465331366908035709767", "6299466490413419527528060929065313571971675302891312", "23243297458011263451861987928588293520022218087828230288", "62101942684066541204453832455816815438182049625435279204488", "120127547020442454023881434479680194723661359437348840609052798", "167671462650605186481604100302187907955931408936160427606658046480", "167799664013981301927907464649022542230075776405152443948615137924777", "119279234106618738418519322946366414856827838172899814841856840731903094", "59477869774199932446650831442149210970493970360512712178751566371376445662", "20478675833501502035170130313412941600643570215140324465570229889080660779422", "4775041276617627478673305548678045551016005866622100940675691161775122261420444", "736550973856121202351836877936681014801516232243435016300853456291278741634588346", "73078857233812331239951719805644587335942750664662747339310323681656094871027699002", "4510093394012912688183443244584617932630764339252266677537812422143446576938670361990", "166313611255899899779218182126677692892244245837992109700205844520483902272506914363176", "3490299336898053852509901088294458321802661159839772440410526201234480241681408107684688", "39250329459059040608132802189276636731080268889822895784547391475298725705292764420956300", "219031465959668931118617879359325447397370214868207109282804729222256909233759746098268332", "547157245358405193800193538538554630903704139318972452478595098976412515718201308186826289", "527136900711873061543356936490755440983264863323846229280329895604478639128707763389840402", "153867143822261048347025663021040800007597578087080948903516209401430571349134000279510970"},
    {"39916800", "234604337741356", "520356670444274517688", "580118387842736957022347041", "375174051427933212608702971856814", "153339234384940346512021348752018853851", "41903293494781170703863413663728379833107772", "7962691332276605250463800514716129196941892913368", "1082370689885259250166498917001785211330216132632347428", "107453729185289455572057276040935494229570264010831541340119", "7911420296072923471482584365908465057679899234192085509960883086", "436850934414537898369956197150825499837515286007865288509178284731562", "18234294807523574622394554428374001559915160208552864086277172020197442078", "578330787794596711052307345257668993589376501608400228155500948731998084162421", "13978001924547050330542400720175800722253939439554959511602790230328404701349725570", "257665962541616261561837078358400810202761997864369934084318558133603108087364377934189", "3618794611817134496801526789358206223779525579940827054974463737219712975435365823195244880", "38615080967905738902430015291641283363393858789615229972633188808226682422062701845886313433409", "311669402448831761755075678738456547202757278675965516005358666477578093615792222361041174538746126", "1891081861415244628349164941926485956684207944282230081178720521973439126058011066661706534680913235021", "8558781066340538567273296157155403053416476222743247256486680460659703737890643513105231712596762480329326", "28619319194976404772883255697713028222173736770391767270618074844959390468106880638107322857395932266541504878", "69909591198642794401993301949560412974018567898879354022405909725149361258465063008144384355847383855378186458484", "123114855330990378908875057300667913440901192038252389341036049906544482922009009713281659578797221005242460136075607", "153947702742223637546534429153916616917525104938020072989462679982660324954787762397183531307899668202066936264983546722", "134330287995768377217192489844672615000881154864009972898942144169958950638839302610883116012700127650036419717632360138287", "80191376116328800512491211405718723001870016575663965130759774454550443998670460657582122817143273819286975655630221762046530", "32025752457841780646289331666605988803451598329637689934589820024597371368976581039118682975446811216636124577467145629221488347", "8341629594915085090474511722767440060575783124625069234068826834053629202444539102845769425836355796368252559739241442724161958894", "1376682847327502498754430158331054857449194070966982462250141026235344425469181781785811346920576952867411648934568333081703415817213"},
    {"479001600", "35124684548865014", "987631036763487449959276", "14154926286618006329785279377249", "119353340566712042755154297655748708260", "645479023255398160221781741622341316059866027", "2371139834909331280071529780184806364639464133890328", "6160761815397161403252078059803922255513733996086826866656", "11663211069244440084325893565169629059689397158887710124804810164", "16452577173533215457740811605259216080578825905922759678635402009023554", "17592578446076233818755685192754467827050151206997854534254275901973355175508", "14449384544541780064696850428376473723939641391070690123815894939045710330511067388", "9209109524209824660829249665371137243259153868373620834490959049065671641068230201760998", "4589880918861118847391475666510022489037035714524880700770181863433542483023916151422001129996", "1799269913503624252962210706501898518349577517269113888949179999380519869050895864051456103635090054", "557005889621408662958170596001467811795955754783131960807610357507701540316943659156858765544522662460710", "136523618571494268585262213476859728629605446716517573392366671420476784893664644582604941292625171130888680794", "26526823663035623048932799158779958435417937012510598704964668428499290054424214311532249358692992678811775802724337", "4086176639323623045411688636507249510140643779752531726794370360628784798438711616927633614371704085981624284101490884668", "498476789907766540013186595681242445344209933273251367187295944837337214015855318152220813843537932603650854229288139777951953", "48056469194081743432518173361525260783681224256168387596184908888384431719095788427876932400752604405989046571170681913947626265430", "3649883902335746391114079667188135347340141984977928589297019681089223562076245366995458225766279401460497512774000780520418401810573650", "217487709559915203200158118159445709436129347253947050886213611926444773518842920316549492469888141717482039249639594864632993576810549734872", "10115730925280461682047779147270970756774987232476634182734551277729573098118271554256890032418600845758647504629830898956668167398727704607460852", "365017301863521168844351263004338244519168383619115889336989233832499717063757346237975639156015919715976019108459510507525039520102052628792912931520", "10145937242225313324798783574635213703299250665087298843179725763449029925195380914532051408095138574982340667208744600294935327959321219287435641905170329", "215473747316049668047781112533913249022329021874824948611842542824343012126447684998580149775605089315662245156914609216439875320042110066330073343765530270414", "3464328963100936357681879821610317080607713297092830564654305132989260614438310115618270592490328686617283747087304388813317445957179596602842027878810843882724666", "41733621914467568026736302502857664252357333254972526750057753681670555919767505659268398063905909391119679169358452384744563056173754347347149866032979112258636708522", "372403432053425301990891222089818488903234566915701977343768634905624989887027472210041099374130342097141124225579320251889338946104170405767925405847565490920267749114385"},
    {"6227020800", "6129493313430487347", "2342730806596452581568991862", "461335641519976906973085475787184206", "54017575718626458098851573106305476467462466", "4101457236906366689799357892619157709910998052662398", "213985719343826736012034819728621281602456102266629070440250", "7993976208811343501177473000040825669767152654013976886519558464972", "220464824517748578594425773332763740563645790120060577476143349452536931508", "4594605427652610257526832872658655183029199448380821046506747775116754716371830070", "73687107506597053303168520713133836577220493092279602720739814768704219673509157221006118", "922604994345819516926707775873474911469335879564388249993104737818851589680188223414660148561824", "9122177155247293627073330441709902631747198802793007763595402870730425256545319419631668093526339787446", "71881201686967776301079450274682324713474205345569806745937985598952037434602838547355046629307331035639142212", "454706297168854041528506197134685983988941668867437349135588759837132681585622326551499890387637950395090509737200534", "2322405332043360076743796240530494018678208324312820758273118692279194367012927767702369951289257008918544774093998445637813", "9619667192474899786249501850281391186131385327450686902453268783564036815355747800844876693608671982285271668931230049913418813176", "32421197717483145752891512321491309855578029741989982074716720070970603040171887253675091504209865296296628945089954936847299976609649896", "89113660485319978401136901982862989975930549700303318378406425295381778624815577454125861771267452273986229411090153866310370541894817032737920", "200040109234055063942196436441185083701903996492039620049116996453009806982477841518659395729458516791017004801474536975480715167254487356512013985466", "366948572268809874400859119650293195355621102257836746747808878837881873639961895468240200670491130373797360775833978814057809583330277808680086797918147132", "549969871166696701511812575815635771935154621502165904703681835008815867255156686683292909910617823458642944602712137385733946077134859374064669925465934023725094", "672884656845132415188313169407144209355658181009526560015012502793252486156183726385788007203500937790996099027341480047191375916220614905057157221425188122234356915206", "671026411584368709442187912299113560038530596680285656927822571876467714364761260116948155520657709240187764917871848729973394070890356400987170292107101999901506869597602814", "544229816760052951401907232039026181328305793157641497621585890542221619379936205640650154545616041783607112486181761590306968739721643981819918098232545430607211738603650276488210", "357964195729798555843486668306403170639629095263449730590667805871418350031150835768547896889672154395760417360917880316673687880080219903211842543290896476871348103566641423623094143890", "190287776066878926331936058484185926059908292789548363456210518693422158361270857348339450371241840991882867094993015274884940632730341076492152879033619451925644054724321026788450862621065086", "81419133034743999890012196089941332572187032210422887165032487475493680041476346525037785183615051561698649357267798002202898562989642076246512330810224590727008319528438024376033462199822783974801", "27909202501571774104353995977460354301731304524641578634602633362953877248409770591705479585119098741390356689954310204083038384462981378279558472295264431088421364197990477131689197557514822791674775586", "7623670735599093959117817528875389622651146306526037450867172946927474950617357123003431445368909574107168943942060514687407723312487552810813722630553776967682989516245748393040954229921997042000355254852520"},
    {"87178291200", "1234186412048962136867", "6853573288421812913739520081046", "19776300977721339217706755509443180083086", "34213018706120859100083120861015134478772865010222", "38707256818770227951539887233593916909516780966918265552108", "30356837066224432930647730994180796299323780575863001460762695389262", "17205442092014421254220589965401815690387886062968951841251592610749306589336", "7269656957497232940502411096280804310759483280003342603122468336915138545088396261792", "2345251691557967274146745117939053396627787376373134464407437213212685344399177453244133484054", "588674939811035060743747871643932864622018034375649476611970986546451116690547175091591466540622201646", "116714989370041220648437401560275092592973378771836808069497381306337634473909613650429703103320453809813191570", "18503570936145944298192366322662765378617871711992060767960396052470358287374365122970862847388510320571387691965517036", "2369204688245536135141892685840946650245230788691848890871081371667489659535459155944657234075809593532601310265923688708016260", "247017711464356197670299890619222980616408735724172898761699853142230202073766432537149526474512978218891999968689862711268223942791884", "21113183482153121437628760321823758956605813220839187076933557307160128588676339447697055620289238734204865000630839263767223055359805196516636", "1487537806578797287019018206395704149401618303608066902799233745353270233321975541934538896067699328706097395811367036884376893417552143970923427326698", "86777415934740482711798967511720620620466991363251862093769893554400056126108646139522014558707535867391065090871320237972068366454223235858951261090413479412", "4206439544874600895607989055231992979584723950362275765915049623151816663781577750979089037207120170389756013075779646957621325438019593044710931041085098004094444308", "169900212024915264835783174318581501938304977327905530202547610300385560946089552203507939139865553764694149512738626028297724018831860633244341027104415991974062622371291850", "5729829861617400062098745735024436318201478528488392042969564104297385622075689260479349178260856488722980552739518620133254025770423824343142013739454596065417589698076924732254436", "161577273717390371645423452912665261810640601221498987615251997413857121904270374533113156752996266343595842124576920721836143310911798260507302225880149750812360200943677521039254631493784", "3813119989805676949972567981921483879797514287734620806840324900507167814364188031604445038212503572129763299653908236473507549746553982974394039765842003413966980811201975166340145335981989383268", "75332209634864255606449748179725768742106115352603009689045372685249623387604118822811735558719156972360503526687915136201032747811368497568196181503248029162141992227142645827589730663364203900214203899", "1245666394370401951352457193688436429288011881969982308488254010651728089537582711795670104884843025497182678157608001562731197808258487525280441360102013073973137565316414126984130306938013612027248587928591394", "17228936495448834734961731450512292933073198891343098920293617985592917394274303136973555020639797891131937996381257572393353634633134565887135362084749390221445742060173513285459355369438317154967870172337904369566998", "199098968459115274629516617924251191447054660758875354504562732595402649984448148185235205492622630651150655806294773157048996442972624807019076102385380787532817402337182286680512165261430529677313614401790486242272212031690", "1919383798078270086448363214834177256196505367817565795812771100902269027877238812849511010190043092121919773939595177237973481755511606647332301684804251320734997465651259984111969004115811634706614138883284480894556921656906894564", "15405684867134684818452832295848444943622814103265333853066846584877228615733434414270403983656339954840452083588106084365871871010312333410798837110653976470037427673193874741721658126534156984783014675365581093992991328176564211522000394", "102704667662752112666113738008167905668228182681969408308819076635610752587858546832428226778231919534946609532054480316780846507775801553764539432913917332995504418620710055985230727867418220248448560517515296778472539071326440945790903637463079"},
    {"1307674368000", "284156251297196944178741", "24424794292884584945672084747811682", "1098485386402439836239874093272530584683557002", "29816311521074417882484419538734440618588680794938241634", "532813316102979001933510408377968684972101235303520820353045886606", "6645945787123076609617096559074800966995644194165737240446999451478462222112", "60340064000822686354050392715483916275731552377131838555680745260520944483606737541288", "411493980260189969285335341236497256185128340222288710104946732849813397388777439598799949560582", "2159659752741814763696923925756369656668358868472241529908057206976552593408432170364474753736120617133639", "8892788073388681436073601275045174615718568648759796090678229307567902762335792868668721234168847756732817864235358", "29179343924498793846717117850510271991450778293657590091146730545716234459183609419378216118434980044224277023697845510666681", "77272858043219478279082380154352482268594529583303117061864123695570127379899559491306845727048426635167674106064780672929016721928530", "166903504498799481251303570079607394817385585141110166767894204747089234225053375488187287979489840459489049537232804520431429342896939995297057", "296620900725854019940505389253452685073223782965486661601154020265420266368001585170311848392190872888716935322777160157890350623573438518012657624367454", "436944687148060493097374155345598072372761058995303025315491962113260373259448932803061446692016224538614500339714263030588524852266306616611748734470825318730941", "536805273678210545251806770236152590249410875289320037741214527481467684855777054899022753725651873138407837840456827801662506524583457754842177124852185650686987286868380", "552863593701692840393336404601483577258827606993134771917902043698485771001317499774602615139933961161439846453529242841771580081301489917847730924151120910829325354292075122905533", "479409704099331214034888915640956605621284747542539786625328269152178986146670156997789666599124070325599516891663560653993407600934013147443667398269146019498811545790062647738269590989166", "351269976959578987702693318192676900308604127212911707449863671677784681755480978073431677537236136020257985737846292726875963824875992300145956473679067376211118524172375448798839299285139476047339", "218121717294799043312721213092716017687716773356116912446634382818635987634425855933910054395376679094601798316249229279432190008034928568393825318620910020329373072453552714349363605626779212086409467270520", "115056409541961156523951981666733819462266095080308564234667570757390914828971551159083576821419312495063791553180869877100821108729503194117147828146608369492871663918191901296950334532537638691909494382157457592574", "51651707808714923788635435040507310265046419374692252685862166633845083690105111446916828664928947652675893099477212596793715064455816359497867750167640213019671464892479366117013934835967466038767610162772733190037471344302", "19761807110519166031286575153662057278128259777108807402760710366078084258293993186721588975926109125909592201331276394572184568419968156766894632206802777524978204716378987492248715278919076719391169374681028094357988243765683798060", "6449973234537742941746132614817189437278301226752955604158215927334629543922746809875410755476291494920816983610393113448657178472904902344156749648980445183872848687655417481027586927530579269707636418397576533197931251819875883575752816826", "1796918662447623326548586448730760095854238727847639435232810519928650668778232022700231263402269421009708553784389451433125294723215043185616190401155344761784653064327518047123900695333078535879902753737098122780572831530131668869873965550851637835", "427393735866244606128693481483753987087569934554385475226578580471575904824548430435150395904134110413047015507698379783198535240396803935796827957351494813646166174646441343389337583823913427819982392541989624479494722934474591749985500821788240023489772844", "86775331396642357437088190013810250014502458203466896487423972732632981499654636614165758225948753143018905611156059720593345302170964294264983177996520413126940799499083780940407716273444300504729774191843151300216307633347256032499482507346565390563996798532693467", "15032411382962420815429896960652311021381489880624288589634140547296904943677063171195144277979721297645089335886511204174666440373421476919249943639849809336798803761010352339722736263477479632781046941513607320476640646526431843369188987359883681308002007303006417100724920", "2220157988868512438084536431262941307429737293898812661902608547612069015613226300009353148235287041905775548025276462673613526975175768386762647022507262400263613998019460718254720149323740621266919018368725687296455745325872911692390107525464975124861600711474660575356134783513373"}
};

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m, mod;
    cin >> n >> m >> mod;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << gaojingduqumo(biao[i - 1][j - 1], mod) << " ";
        }
        cout << '\n';
    }
}

AC Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define uint unsigned int

const int N = 16;   // n 最大值
const int S = 125;  // 对应最大逆序数上界
const int M = 35;   // m 最大值

int n, m, mod;

// 模运算加法
inline int add(int a, int b)
{
    a += b;
    if (a >= mod) a -= mod;
    return a;
}

// 模运算乘法
inline int mul(ll a, ll b)
{
    return (int)((i128)a * b % mod);
}

// 三维 DP 数组
static uint f[S][S][M];   // 主 DP
static uint g[S][S][M];   // 搬移态
static uint h[S][S][M];   // 前缀和态
static uint t1[S][S][M];  // 临时卷积态
static int out[N][M];     // 输出矩阵

// step(): 执行一次“长度扩展”操作
void step(int len)
{
    // 初始化辅助数组
    for (int i = 0; i <= len; i++)
    {
        memset(h[i], 0, sizeof(h[i]));
        memset(t1[i], 0, sizeof(t1[i]));
    }

    // 计算搬移态 g → h
    for (int i = 1; i <= len; i++)
    {
        for (int j = 1; j <= len; j++)
        {
            for (int x = 0; x <= m; x++)
            {
                h[i][j][x] = g[i - 1][j - 1][x];
            }
        }
    }

    // 复制搬移结果到 g
    for (int i = 0; i <= len; i++)
    {
        memcpy(g[i], h[i], sizeof(g[i]));
    }

    // 构造二维前缀和 h[i][j][x]
    for (int i = 1; i <= len; i++)
    {
        for (int j = 0; j <= len; j++)
        {
            for (int x = 0; x <= m; x++)
            {
                h[i][j][x] += h[i - 1][j][x];
                if ((ull)h[i][j][x] >= (ull)mod) 
                    h[i][j][x] -= mod;
            }
        }
    }

    // 卷积叠加 f × h → t1
    for (int i = len; i >= 0; i--)
    {
        for (int j = i; j >= 0; j--)
        {
            for (int k = j - 1; k >= 0; k--)
            {
                for (int x0 = 0; x0 <= m; x0++)
                {
                    if (!f[i][j][x0]) continue;
                    for (int y0 = 0; x0 + y0 <= m; y0++)
                    {
                        if (!h[j - 1][k][y0]) continue;
                        ull v = 
                            (ull)f[i][j][x0] * h[j - 1][k][y0] + 
                            t1[i][k][x0 + y0];
                        t1[i][k][x0 + y0] = v % mod;
                    }
                }
            }
        }
    }

    // 合并回主数组 f
    for (int i = 0; i <= len; i++)
    {
        for (int j = 0; j <= len; j++)
        {
            for (int x = 0; x <= m; x++)
            {
                uint v = f[i][j][x] + t1[i][j][x];
                if (v >= (uint)mod) v -= mod;
                v += g[i][j][x];
                if (v >= (uint)mod) v -= mod;
                f[i][j][x] = v;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> mod;

    // 初始状态
    memset(f, 0, sizeof(f));
    f[0][0][1] = 1; // 长度为1的排列数为1

    // n=1 时直接输出
    for (int j = 1; j <= m; j++)
    {
        int v = (j == 1) ? 1 : 0;
        out[1][j] = v;
    }
    for (int j = 1; j <= m; j++)
    {
        cout << out[1][j] << (j == m ? '\n' : ' ');
    }

    int len = 0;

    // 构造长度 2~n 的情况
    for (int i = 2; i <= n; i++)
    {
        memcpy(g, f, sizeof(g));
        for (int t = 1; t <= i - 1; t++)
        {
            ++len;
            step(len);
        }

        // 统计 f[i][j] = 所有二维状态求和
        for (int x = 1; x <= m; x++)
        {
            uint s = 0;
            for (int a = 0; a <= len; a++)
            {
                for (int b = 0; b <= len; b++)
                {
                    if (f[a][b][x])
                    {
                        s += f[a][b][x];
                        if (s >= (uint)mod) s -= mod;
                    }
                }
            }
            out[i][x] = s % mod;
        }

        // 输出第 i 行
        for (int j = 1; j <= m; j++)
        {
            cout << out[i][j] << (j == m ? '\n' : ' ');
        }
    }
    return 0;
}

题解：P9004 [RC-07] Abnormal Permutation Tuples

文章操作

题意简述

思路

AC Code

相关推荐

评论

题解：P9004 [RC-07] Abnormal Permutation Tuples