[JXOI2018]排序问题

发表于
本文字数： 5.7k | 阅读时长 ≈ 5 分钟

$[JXOI2018]$ 排序问题

$Description$

$Solution$

先解释一下题意。

就是给你一个长度为 $n$ 的序列，然后允许插入 $m$ 个数到这个序列中，这 $m$ 个数的取值范围在 $[l,\ r]$ 之间，然后把这个序列排序，然后生成一个关于 $x_i$ 的编号排列，求使这个编号排列有序的操作次数的期望。

首先样例已经给出了解释，操作次数的期望就是成功概率的倒数。

然后考虑怎么去求出这个概率。

很显然对于一个不重的排列，成功的概率就是 $\dfrac{1}{n!}$ ，期望就是 $n!$ 。而对于一个有重复元素的排列，成功的概率则与单个重复元素的个数相关，显然如果某个元素出现了 $k$ 次，那么概率就会变成 $p \times \dfrac{k!}{n!}$ ，期望就会变成 $\dfrac{E(x)}{k!}$ 。

那么为了使期望最大，我们插入的数字显然要使得新的排列单个元素出现次数最大的最小。

看到最大的最小，就要想到二分。

先来考虑暴力贪心的做法，设置一个 $limit$ ，开一个桶记录最开始每个数的出现次数，然后先将当前出现次数最小的增加上去，最后将出现次数 $> 1$ 的逆元；累乘给 $Ans$ ，注意 $Ans$ 初始为 $(n + m) !$ 。

然后考虑二分答案。

二分新排列的元素的最大出现次数。

贪心的放，然后判断次数是否 $<= mid$ 。

二分出最大出现次数后解一个方程，解出有几个被放到 $L$ ，有几个是 $L - 1$ 。

注意最后要补上不在 $l \to r$ 范围内的重复数字的贡献以及 $l \to r$ 范围内的 $>= L$ 的数字的贡献。

其实也不算很难，只是中间蠢了没想到解方程怎么搞 。

就做完了。

$Code:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <bits/stdc++.h>
#include <tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define lowbit(x) (x & -x)
#define debug(x) (cout << "#x = " << (x) << endl)
#define Set(x, i) memset (x, i, sizeof(x))
#define re register
#define For(i, j, k) for(re int i = (j), ED = (k); i <= ED; ++i)
#define foR(i, j, k) for(re int i = (j), ED = (k); i >= ED; --i)
#define Cross(i, j, k) for(re int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 200011;
const ll M = 1e7 + N;
const ll INF = 5e16;
const ll P = 998244353;

ll fac[M];
ll T, n, m, l, r, x[N];

namespace IO {

    inline char gc() {
        static char buf[100000], *p1 = buf, *p2 = buf;
        return (p1 == p2) && (p2 = (p1 = buf) +
            fread (buf, 1, 100000, stdin), p1 == p2)? EOF: *p1++;
    }

    #define dd ch = gc()
    inline ll read() {
        ll x = 0; bool f = 0; char dd;
        for (; !isdigit (ch); dd) f ^= (ch == '-');
        for (; isdigit (ch); dd)  x = x * 10 + (ch ^ 48);
        return f? -x: x;
    }
    #undef dd

    inline void write( ll x ) {
        if (x < 0) putchar ('-'), x = -x;
        if (x > 9) write (x / 10); putchar (x % 10 | 48);
    }

    inline void wrn ( ll x ) { write (x); putchar (' '); }

    inline void wln ( ll x ) { write (x); putchar ('\n'); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using IO::wln;
using IO::read;

tr1::unordered_map <ll, ll> mp;

inline ll power ( ll a, ll b, ll res = 1 ) {
    for (; b; b >>= 1, a = a * a % P) 
        res = (b & 1)? res * a % P: res; return res;
}

inline ll Inv ( ll a ) { return power (a, P - 2); }

namespace Subtask1 {

    inline void main () {
        while (T--) {
            ll A = 0;
            mp.clear();
            n = read(), m = read(), 
            l = read(), r = read();
            For ( i, 1, n ) ++mp[x[i] = read()];
            ll Lim = 0, Ko = m;
            while (Ko) {
                for (int i = l; i <= r && Ko; ++i) 
                    if (mp[i] <= Lim) --Ko, ++mp[i];
                ++Lim;
            }
            ll Ans = fac[n + m];
            For ( i, 1, 300 ) Ans = Ans * Inv (fac[mp[i]]) % P;
            wln (Ans);
        } exit (0);
    }

}

namespace Cesare {

    ll Ko = 0, tot = 0;
    ll a[N], b[N], c[N], cnt[N], Cnt[N];

    inline int Check ( ll x ) {
        ll res = Ko * x;
        For ( i, 1, tot ) 
            if (Cnt[i] < x) res += x - Cnt[i]; 
                // 使元素的出现次数全部 >= x 。 
        return res < m; // 使修改次数变成 m 时找到那个最平均的 x 。 
    }

    void main() {
        while (T--) {
            n = read(), m = read(), 
            l = read(), r = read();
            Ko = r - l + 1, tot = 0;
            For ( i, 1, n ) ++mp[a[i] = b[i] = read()];
    
            sort (b + 1, b + n + 1);
            ll Len = unique (b + 1, b + n + 1) - b - 1;
            For ( i, 1, Len ) {
                cnt[i] = mp[b[i]];
                if (b[i] >= l && b[i] <= r) 
                    c[++tot] = b[i], Cnt[tot] = cnt[i], --Ko;
            }
            
            ll L = 0, R = n + m;
            while (L <= R) {
                ll Mid = (L + R) >> 1;
                Check (Mid)? L = Mid + 1: R = Mid - 1;
            }
            
            ll CC = Ko, S = 0;
            For ( i, 1, tot )  if (Cnt[i] < L) ++CC, S += Cnt[i];
    
            ll Ans = fac[n + m];
            if (CC * L == S + m) 
                Ans = Ans * power (Inv (fac[L]), CC) % P; // 全部均摊，Δt = 0 
            else {
                ll y = L * CC - m - S; // - Δt
                ll x = (1 - L) * CC + m + S; // + Δt
                ll N1 = power (Inv (fac[L]), x);
                ll N2 = power (Inv (fac[L - 1]), y);
                Ans = Ans * N1 % P * N2 % P;
            }
            For ( i, 1, Len ) 
                if (b[i] < l || b[i] > r) 
                    Ans = Ans * Inv (fac[cnt[i]]) % P;
            For ( i, 1, tot ) 
                if (Cnt[i] >= L) 
                    Ans = Ans * Inv (fac[Cnt[i]]) % P;
            wln (Ans);
            
            For ( i, 1, Len ) mp[b[i]] = 0;
        } exit (0);
    }

}

inline void Init() {
    fac[0] = 1;
    For ( i, 1, M - 5 ) 
        fac[i] = fac[i - 1] * i % P;
}

int main()
{
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
    Init();
    T = read(); 
    if (T <= 300) 
        Subtask1::main ();
    return Cesare::main(), 0;
}

/*

*/

题目链接