P4561 [JXOI2018] 排序问题

题意有一个序列现在要在结尾加上mmm个[l,r][l,r][l,r]之间的数求在所有方案中猴子排序每次随机一个排列检查是否有序的次数期望最大次数。思路假设最终的序列中数iii出现的次数是cic_ici​那么合法的ppp的数量为∏ici!\prod_ic_i!∏i​ci​!为了使方案数尽可能少我们需要让 数的个数分配的更平均。求出[l,r][l,r][l,r]之间出现iii次的数有几个按照存在的iii由小到大遍历如果剩余的次数能够把所有次数iii的数的出现次数都变为iii那么把祂们都变为iii否则平均分配。答案为合法的ppp数量比(nm)!(nm)!(nm)!。代码/* Luogu P4561 [JXOI2018] 排序问题 2026-04-09 */#includebits/stdc.husingnamespacestd;namespaceIO{templatetypenameTinlinevoidread(Tx){x0;charcgetchar();boolf0;while(!isdigit(c))c-?f1:0,cgetchar();while(isdigit(c))xx*10c-0,cgetchar();f?x-x:0;}templatetypenameTinlinevoidwrite(T x){if(x0){putchar(0);return;}x0?x-x,putchar(-):0;shortst[50],top0;while(x)st[top]x%10,x/10;while(top)putchar(st[top--]0);}inlinevoidread(charc){cgetchar();while(isspace(c))cgetchar();}inlinevoidwrite(charc){putchar(c);}inlinevoidread(strings){s.clear();charc;read(c);while(!isspace(c)~c)sc,cgetchar();}inlinevoidwrite(string s){for(inti0,lens.size();ilen;i)putchar(s[i]);}templatetypenameTinlinevoidwrite(T*x){while(*x)putchar(*(x));}templatetypenameT,typename...T2inlinevoidread(Tx,T2...y){read(x),read(y...);}templatetypenameT,typename...T2inlinevoidwrite(constT x,constT2...y){write(x),putchar( ),write(y...),sizeof...(y)1?putchar(\n):0;}}usingnamespaceIO;templateintmodstructModint{intz;Modint(){z0;}Modint(intx){x%mod;zx0?xmod:x;}Modint(longlongx){x%mod;zx0?xmod:x;}Modint(shortx){x%mod;zx0?xmod:x;}Modint(charx){x%mod;zx0?xmod:x;}Modint(boolx){x%mod;zx0?xmod:x;}friendModintoperator(Modint t,Modint t2){Modint ans;ans.z(t.zt2.z)%mod;returnans;}friendModintoperator*(Modint t,Modint t2){Modint ans;ans.z1ll*t.z*t2.z%mod;returnans;}friendModintoperator-(Modint t,Modint t2){Modint ans;ans.z(t.z-t2.z)%mod;returnans;}Modintoperator(constintt)const{Modint ans;ans.z(zt)%mod;returnans;}Modintoperator(constintt)const{Modint ans;ans.z(zt)%mod;returnans;}Modintoperator(constModint t){z(zt.z)%mod;return*this;}Modintoperator*(constModint t){z1ll*z*t.z%mod;return*this;}Modintoperator-(constModint t){z(z-t.z)%mod;return*this;}Modintoperator(constintt){z(zt)%mod;return*this;}Modintoperator(constintt){z(zt)%mod;return*this;}Modintoperator(){z,z%mod;return*this;}Modintoperator--(){z--,z%mod;return*this;}Modintoperator(int){Modint ls*this;z,z%mod;returnls;}Modintoperator--(int){Modint ls*this;z--,z%mod;returnls;}friendModintksm(Modint a,intb){Modint ans1;while(b){if(b1)ansans*a;aa*a,b1;}returnans;}friendvoidread(Modintz){intx0;charcgetchar();boolf0;while(!isdigit(c))c-?f1:0,cgetchar();while(isdigit(c))x(x*10llc-0)%mod,cgetchar();f?x-x:0;z.zx;}friendvoidwrite(Modint x){x.z0?x.zmod:0;write(x.z);}};constintmod998244353,maxn200010,maxm10000010;#defineMModintmodM jc[maxnmaxm];intn,m,l,r,a[maxn],cnt_h;structnode{intval,cnt;}h[maxn];mapint,intmp,mpp;voidsolve(){M ans1;mp.clear(),mpp.clear();read(n,m,l,r);intlsmn;for(inti1;in;i)read(a[i]),mp[a[i]];for(inti1;in;i){if(la[i]a[i]r)continue;ans*jc[mp[a[i]]];mp[a[i]]0;}cnt_h0;for(auto[val,cnt]:mp)if(lvalvalr)mpp[cnt];for(auto[val,cnt]:mpp)h[cnt_h]{val,cnt};sort(h1,h1cnt_h,[](node a,node b){returna.valb.val;});h[0].cntr-l1;for(inti1;icnt_h;i)h[0].cnt-h[i].cnt;intnow_cnth[0].cnt;h[cnt_h].val2000000000;for(inti1;icnt_h;i){intch[i].val-h[i-1].val;if(1ll*c*now_cntm){m-c*now_cnt;now_cnth[i].cnt;continue;}intzh[i-1].valm/now_cnt,sym%now_cnt;ans*ksm(jc[z],now_cnt)*ksm(M(z1),sy);for(intji;jcnt_h-1;j)ans*ksm(jc[h[j].val],h[j].cnt);break;}write(jc[ls]*ksm(ans,mod-2)),write(\n);}signedmain(){jc[0]1;for(inti1;i10200000;i)jc[i]jc[i-1]*i;intT;read(T);while(T--)solve();return0;}