题意

题目链接

Sol

首先一种方案的期望等于它一次排好的概率的倒数。

一次排好的概率是个数数题，他等于一次排好的方案除以总方案，也就是\(\frac{\prod cnt_{a_i}!}{(n+m)!}\)。因为最终的序列是一定的，两个序列不同当且仅当权值相同的数排列方式不同。

他的期望为\(\frac{(n+m)!}{\prod cnt_i!}\)，我们希望这玩意儿尽量大，也就是下面的尽量小

显然对于每个\(cnt\)来说，最大值越小越好，可以直接二分，然后check一下是否可行。

具体的贪心策略是每次先填出现次数最少的。

复杂度\(O(nlogn)\)

#include<bits/stdc++.h>

#define Fin(x) freopen(#x".in", "r", stdin);

#define int long long

using namespace std;

const int MAXN = 2e7 + 10, mod = 998244353;

template<typename A, typename B> inline bool chmax(A &x, B y) {return x < y ? x = y, 1 : 0;}

template<typename A, typename B> inline bool chmin(A &x, B y) {return x > y ? x = y, 1 : 0;}

template<typename A, typename B> inline A mul(A x, B y) {return 1ll * x * y % mod;}

template<typename A, typename B> inline void add2(A &x, B y) {x = x + y >= mod ? x + y - mod : x + y;}

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N, M, fac[MAXN], L, R, a[MAXN], date[MAXN], num, cnt[MAXN], pl, pr, l, r;

int fp(int a, int p) {

    int base = 1;

    while(p) {

        if(p & 1) base = mul(base, a);

        a = mul(a, a);  p >>= 1;

    }

    return base;

}

int inv(int x) {

	return fp(x, mod - 2);

}

int check(int lim) {

	int tot = 0;

	tot = lim * (R - L - (pr - pl));

	if(tot > M) return tot;

	for(int i = pl; i <= pr && tot <= M; i++)

		tot += max(lim - cnt[i], 0ll);

	return tot;

}

void solve() {

	N = read(); M = read(); L = read(); R = read();

	num = 0;

	for(int i = 1; i <= N; i++) a[i] = read(), date[++num] = a[i], cnt[i] = 0;

	sort(a + 1, a + N + 1);

	sort(date + 1, date + num + 1);

	num = unique(date + 1, date + num + 1) - date - 1;

	for(int i = 1; i <= N; i++) a[i] = lower_bound(date + 1, date + num + 1, a[i]) - date, cnt[a[i]]++;

	pl = lower_bound(date + 1, date + num + 1, L) - date;

	pr = upper_bound(date + 1, date + num + 1, R) - date - 1;

	l = 0, r = N + M;

	while(l < r) {

		int mid = l + r >> 1;

		if(check(mid) <= M) l = mid + 1;

		else r = mid;

	}

	int ans = fp(fac[l - 1], R - L - (pr - pl));

	for(int i = 1; i <= num; i++)

		if(i >= pl && i <= pr) ans = mul(ans, fac[max(cnt[i], l - 1)]);

		else ans = mul(ans, fac[cnt[i]]);

	ans = mul(ans, fp(l, M - check(l - 1)));//把少了的补上

	cout << mul(fac[N + M], inv(ans)) <<  '\n';

}

signed main() {

	fac[0] = 1;

	for(int i = 1; i <= (int) 2e7; i++) fac[i] = mul(i, fac[i - 1]);

	for(int T = read(); T--;  solve());

	return 0;

}

/*

2

3 3 5 7

1 3 4

3 3 1 2

1 3 4

*/