BZOJ5322: [JXOI2018]排序问题

传送门

不难看出期望就是 \(\frac{(n+m)!}{\prod_{v=1}^{max}(cnt_v!)}\)，\(cnt_v\) 表示 \(v\) 这个数出现的次数。

贪心就是直接把 \(m\) 个数字每次选择一个 \(cnt\) 最小的加入，使得最后 \([l,r]\) 内每个数字出现的次数尽量平均。

直接按照数字出现的次数排序，从大到小枚举平均的次数是多少即可。

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn(2e5 + 5);

const int mod(998244353);

inline void Inc(int &x, const int y) {

    x = x + y >= mod ? x + y - mod : x + y;

}

inline int Pow(ll x, int y) {

    ll ret = 1;

    for (; y; y >>= 1, x = x * x % mod)

        if (y & 1) ret = ret * x % mod;

    return ret;

}

int n, m, l, r, a[maxn], val[maxn], cnt[maxn], tot, ans;

int fac[(int)1e7 + maxn];

inline void Solve() {

	int i, len, facn;

	scanf("%d%d%d%d", &n, &m, &l, &r), len = r - l + 1;

	for (i = 1; i <= n; ++i) scanf("%d", &a[i]);

	sort(a + 1, a + n + 1), facn = fac[n + m];

	for (i = 1, tot = 0; i <= n; ++i) {

		if (a[i] != val[tot]) val[++tot] = a[i], cnt[tot] = 0;

		++cnt[tot];

	}

	n = tot, ans = 1, tot = 0;

	for (i = 1; i <= n; ++i)

		if (val[i] < l || val[i] > r) ans = (ll)ans * fac[cnt[i]] % mod;

		else cnt[++tot] = cnt[i], m += cnt[i];

	sort(cnt + 1, cnt + tot + 1);

	for (i = tot; ~i; --i) {

		if (m / len >= cnt[i]) {

			ans = (ll)Pow(fac[m / len + 1], m % len) * ans % mod * Pow(fac[m / len], len - m % len) % mod;

			break;

		}

		m -= cnt[i], --len, ans = (ll)ans * fac[cnt[i]] % mod;

	}

	ans = (ll)Pow(ans, mod - 2) * facn % mod;

	printf("%d\n", ans);

}

int main() {

	int i, mx = 1e7 + 2e5;

    for (i = fac[0] = 1; i <= mx; ++i) fac[i] = (ll)fac[i - 1] * i % mod;

	scanf("%d", &mx);

	while (mx--) Solve();

	return 0;

}