题目
自己写的必须要写题解啊！
先考虑什么是期望轮数。
显然可以从样例观察到。
轮数的概率 \(P\) 是知道的（为 \(\frac {合法的}{总数}\)），且每次操作都是独立的（合法表示 \(b\) 有序可以结束算法）。
那么若第一次就成功次数为 \(1\)。
若第一次失败，那么由于操作是独立的，那么期望次数任然为 \(E\)。
\(\therefore E=1+(1-P)*(E-1)\)
\(\therefore E= \frac {1}{P}\)
所以期望为 \(\frac {总数}{合法的}\)
而我们要求 \(E\) 最大，也就是合法的尽量少。
考虑怎么样是合法的。
若一个数 \(x\) 出现了 \(y\) 次，那么它在匹配时可以随便排所以 \(x\) 的合法匹配为 \(y!\)。
所以合法的总数为 \(\prod_{}{cnt_{a_{i}}!}\)
而设现在贡献为 \(sum\)，若对于两个数次数一样为 \(cnt\)，给两个分别加 \(1\) 的话，\(sum \gets sum \times (cnt+1) \times (cnt+1)\)，若只加一个，\(sum \gets sum \times (cnt+1) \times (cnt+2)\)。
观察到给两个分别加 \(1\) 是更优的（其他情况同理）。
那么直接贪心加给小的次数。
注意对于不在 \([l,r]\) 的值次数为 \(0\)。
还有这道题似乎卡 unordered_map，直接用 map 更快。
所以为什么我跑这么慢啊？
code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,l,r) for(ll i=(l);i<=(r);++i)
#define per(i,r,l) for(ll i=(r);i>=(l);--i)const ll N=1e6+5,M=2e7+5,mod=998244353;
ll n,m,l,r;
ll a[N],fac[M],inv[M];
ll pom(ll x,ll y){ll res=1;for(;y;y>>=1,x=x*x%mod) if(y&1) res=res*x%mod;return res;}
map<ll,ll>cnt;
map<ll,ll>mp;
void solve(){cnt.clear();mp.clear();cin>>n>>m>>l>>r;ll mm=r-l+1;rep(i,1,n){cin>>a[i];if(!cnt[a[i]]++&&l<=a[i]&&a[i]<=r) --mm;}ll all=fac[n+m],sum=1,gs=0;for(auto u:cnt){sum=sum*fac[u.second]%mod;if(l<=u.first&&u.first<=r) mp[u.second]++;}if(mm) mp[0]=mm;auto v=mp.begin();auto calc=[](ll k,ll a,ll b){return pom(fac[b+(k/a)]*inv[b]%mod,a)%mod*pom(b+(k/a)+1,k%a)%mod;};for(auto u:mp){if(!m) continue;gs+=u.second;if(++v==mp.end()){sum=sum*calc(m,gs,u.first)%mod;}else{ll d=min(m,gs*(v->first-u.first));sum=sum*calc(d,gs,u.first)%mod;m-=d;}}cout<<all*pom(sum,mod-2)%mod<<'\n';
}
int main(){cin.tie(0)->ios::sync_with_stdio(false);fac[0]=1;rep(i,1,M-1) fac[i]=fac[i-1]*i%mod;inv[M-1]=pom(fac[M-1],mod-2);per(i,M-2,0) inv[i]=inv[i+1]*(i+1)%mod;ll T=1;cin>>T;while(T--) solve();return 0;
}