欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P4561 [JXOI2018]排序问题(二分 期望)

程序员文章站 2022-04-09 19:51:16
题意 "题目链接" Sol 首先一种方案的期望等于它一次排好的概率的倒数。 一次排好的概率是个数数题,他等于一次排好的方案除以总方案,也就是$\frac{\prod cnt_{a_i}!}{(n+m)!}$。因为最终的序列是一定的,两个序列不同当且仅当权值相同的数排列方式不同。 他的期望为$\fra ......

题意

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
*/