题意
有一个序列，现在要在结尾加上mmm个[l,r][l,r][l,r]之间的数，求在所有方案中，猴子排序（每次随机一个排列，检查是否有序）的次数期望最大次数。
思路
假设最终的序列中数iii出现的次数是cic_ici，那么合法的ppp的数量为∏ici!\prod_ic_i!∏ici!，为了使方案数尽可能少，我们需要让 数的个数分配的更平均。
求出[l,r][l,r][l,r]之间出现iii次的数有几个，按照存在的iii由小到大遍历，如果剩余的次数能够把所有次数<i<i<i的数的出现次数都变为iii，那么把祂们都变为iii，否则平均分配。
答案为合法的ppp数量比(n+m)!(n+m)!(n+m)!。
代码
/* Luogu P4561 [JXOI2018] 排序问题 2026-04-09 */#include<bits/stdc++.h>usingnamespacestd;namespaceIO{template<typenameT>inlinevoidread(T&x){x=0;charc=getchar();boolf=0;while(!isdigit(c))c=='-'?f=1:0,c=getchar();while(isdigit(c))x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typenameT>inlinevoidwrite(T x){if(x==0){putchar('0');return;}x<0?x=-x,putchar('-'):0;shortst[50],top=0;while(x)st[++top]=x%10,x/=10;while(top)putchar(st[top--]+'0');}inlinevoidread(char&c){c=getchar();while(isspace(c))c=getchar();}inlinevoidwrite(charc){putchar(c);}inlinevoidread(string&s){s.clear();charc;read(c);while(!isspace(c)&&~c)s+=c,c=getchar();}inlinevoidwrite(string s){for(inti=0,len=s.size();i<len;i++)putchar(s[i]);}template<typenameT>inlinevoidwrite(T*x){while(*x)putchar(*(x++));}template<typenameT,typename...T2>inlinevoidread(T&x,T2&...y){read(x),read(y...);}template<typenameT,typename...T2>inlinevoidwrite(constT x,constT2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}}usingnamespaceIO;template<intmod>structModint{intz;Modint(){z=0;}Modint(intx){x%=mod;z=x<0?x+mod:x;}Modint(longlongx){x%=mod;z=x<0?x+mod:x;}Modint(shortx){x%=mod;z=x<0?x+mod:x;}Modint(charx){x%=mod;z=x<0?x+mod:x;}Modint(boolx){x%=mod;z=x<0?x+mod:x;}friendModintoperator+(Modint t,Modint t2){Modint ans;ans.z=(t.z+t2.z)%mod;returnans;}friendModintoperator*(Modint t,Modint t2){Modint ans;ans.z=1ll*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=(z<<t)%mod;returnans;}Modintoperator>>(constintt)const{Modint ans;ans.z=(z>>t)%mod;returnans;}Modint&operator+=(constModint t){z=(z+t.z)%mod;return*this;}Modint&operator*=(constModint t){z=1ll*z*t.z%mod;return*this;}Modint&operator-=(constModint t){z=(z-t.z)%mod;return*this;}Modint&operator<<=(constintt){z=(z<<t)%mod;return*this;}Modint&operator>>=(constintt){z=(z>>t)%mod;return*this;}Modint&operator++(){z++,z%=mod;return*this;}Modint&operator--(){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 ans=1;while(b){if(b&1)ans=ans*a;a=a*a,b>>=1;}returnans;}friendvoidread(Modint&z){intx=0;charc=getchar();boolf=0;while(!isdigit(c))c=='-'?f=1:0,c=getchar();while(isdigit(c))x=(x*10ll+c-'0')%mod,c=getchar();f?x=-x:0;z.z=x;}friendvoidwrite(Modint x){x.z<0?x.z+=mod:0;write(x.z);}};constintmod=998244353,maxn=200010,maxm=10000010;#defineMModint<mod>M jc[maxn+maxm];intn,m,l,r,a[maxn],cnt_h;structnode{intval,cnt;}h[maxn];map<int,int>mp,mpp;voidsolve(){M ans=1;mp.clear(),mpp.clear();read(n,m,l,r);intls=m+n;for(inti=1;i<=n;i++)read(a[i]),mp[a[i]]++;for(inti=1;i<=n;i++){if(l<=a[i]&&a[i]<=r)continue;ans*=jc[mp[a[i]]];mp[a[i]]=0;}cnt_h=0;for(auto[val,cnt]:mp)if(l<=val&&val<=r)mpp[cnt]++;for(auto[val,cnt]:mpp)h[++cnt_h]={val,cnt};sort(h+1,h+1+cnt_h,[](node a,node b){returna.val<b.val;});h[0].cnt=r-l+1;for(inti=1;i<=cnt_h;i++)h[0].cnt-=h[i].cnt;intnow_cnt=h[0].cnt;h[++cnt_h].val=2000000000;for(inti=1;i<=cnt_h;i++){intc=h[i].val-h[i-1].val;if(1ll*c*now_cnt<=m){m-=c*now_cnt;now_cnt+=h[i].cnt;continue;}intz=h[i-1].val+m/now_cnt,sy=m%now_cnt;ans*=ksm(jc[z],now_cnt)*ksm(M(z+1),sy);for(intj=i;j<=cnt_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(inti=1;i<=10200000;i++)jc[i]=jc[i-1]*i;intT;read(T);while(T--)solve();return0;}
