我们令$sum_i$表示数字i在加完数字的数列中出现的次数，那么答案显然为$\dfrac_{(n+m)!}{\sum_{i=0}^{\infty}sum_i!}$

不难发现，当每次添加的数为$[l,r]$中出现次数最少的数时，答案就是最小的了。

然后就没了

貌似我常数比较大在loj上是997ms过的。。。。。。

 

 1 #include<bits/stdc++.h>
 2 #define M 20000005
 3 #define L long long
 4 #define MOD 998244353
 5 using namespace std;
 6 const L INF=2e9;
 7 
 8 map<int,int> mp;
 9 L num[M]={0},nn=0;
10 L n,m,l,r;
11 
12 L pow_mod(L x,L k){L ans=1; for(;k;k>>=1,x=x*x%MOD) if(k&1) ans=ans*x%MOD; return ans;}
13 L fac[M]={0};
14 
15 L Main(){
16     nn=0;
17     mp.clear();
18     scanf("%d%d%d%d",&n,&m,&l,&r); 
19     L F=fac[n+m];
20     for(L i=1;i<=n;i++){
21         L x; scanf("%d",&x);
22         mp[x]++;
23     }
24     L mul=1;
25     for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){
26         L x=it->first,y=it->second;
27         if(!(l<=x&&x<=r)) mul=mul*fac[y]%MOD;
28         else num[++nn]=y;
29     }
30     num[nn+1]=0;
31     sort(num+1,num+nn+1);
32     if(nn) reverse(num+1,num+nn+1);
33     L lr=r-l+1; num[0]=INF;
34     for(L i=nn;~i;i--){
35         L mns=1LL*(lr-i)*(num[i]-num[i+1]);
36         if(mns<=m) {m-=mns; continue;}
37         L up=num[i+1]+m/(lr-i);
38         L yu=m%(lr-i);
39         L mul2=pow_mod(fac[up+1],yu);
40         L mul1=pow_mod(fac[up],lr-i-yu);
41         mul=mul*mul1%MOD*mul2%MOD;
42         for(int j=i;j>=1;j--){
43             mul=mul*fac[num[j]]%MOD;
44         }
45         break;
46     }
47     mul=pow_mod(mul,MOD-2);
48     cout<<F*mul%MOD<<endl;
49 }
50 
51 int main(){
52     fac[0]=1; for(L i=1;i<M;i++) fac[i]=fac[i-1]*i%MOD;
53     L cas; cin>>cas;
54     while(cas--) Main();
55 }