洛谷P4561 [JXOI2018]排序问题

### 1.1 题目描述
九条可怜是一个热爱思考的女孩子。
九条可怜最近正在研究各种排序的性质，她发现了一种很有趣的排序方法：gobo sort！
Gobo sort 的算法描述大致如下：
• 1. 假设我们要对一个大小为 n 的数列 a 排序。
• 2. 等概率随机生成一个大小为 n 的排列 p 。
• 3. 构造一个大小为 n 的数列 b 满足 bi = api，检查 b 是否有序，如果 b 已经有序了就结
束算法，并返回 b ，不然返回步骤 2 。
显然这个算法的期望时间复杂度是 O(n × n!) 的，但是九条可怜惊奇的发现，利用量子的
神奇性质，在量子系统中，可以把这个算法的时间复杂度优化到线性。
九条可怜对这个排序算法进行了进一步研究，她发现如果一个序列满足一些性质，那么
Gobo sort 会很快计算出正确的结果。为了量化这个速度，她定义 Gobo sort 的执行轮数是步骤 2 的执行次数。
于是她就想到了这么一个问题：
现在有一个长度为 n 的序列 x ，九条可怜会在这个序列后面加入 m 个元素，每个元素
是 [l, r] 内的正整数。她希望新的长度为 n + m 的序列执行 Gobo sort 的期望执行轮数尽量的
多。她希望得到这个最多的期望轮数。
九条可怜很聪明，她很快就算出了答案，她希望和你核对一下，由于这个期望轮数实在是
太大了，于是她只要求你输出对 998244353 取模的结果。
### 1.2 输入格式
第一行输入一个整数 T，表示数据组数。
接下来 2T 行描述了 T 组数据。
每组数据分成两行，第 1 行有四个正整数 n, m, l, r ，表示数列的长度和加入数字的个数和
加入数字的范围。
第 2 行有 n 个正整数，第 i 个表示 xi 。
### 1.3 输出格式
输出 T 个整数，表示答案。

### 1.4 样例输入
```
2
3 3 1 2
1 3 4
3 3 5 7
1 3 4
```
### 1.5 样例输出
```
180
720
```
### 1.6 样例解释
对于第一组数据，我们可以添加 {1, 2, 2} 到序列的最末尾，使得这个序列变成 1 3 4 1 2 2，
那么进行一轮的成功概率是 1
180 ，因此期望需要 180 轮。
对于第二组数据，我们可以添加 {5, 6, 7} 到序列的最末尾，使得这个序列变成 1 3 4 5 6 7，
那么进行一轮的成功概率是 1
720 ，因此期望需要 720 轮。
1.7 数据范围与约定
对于 30% 的数据，T ≤ 10,n, m, l, r ≤ 8。
对于 50% 的数据，T ≤ 300, n, m, l, r, ai ≤ 300。
对于 60% 的数据，∑r − l + 1 ≤ 10^7。
对于 70% 的数据，∑n ≤ 2 × 10^5。
对于 90% 的数据，m ≤ 2 × 10^5。
对于 100% 的数据，T ≤ 10^5
, n ≤ 2 × 10^5
, m ≤ 10^7
, 1 ≤ l ≤ r ≤ 10^9。
对于 100% 的数据，1 ≤ ai ≤ 10^9
,
∑n ≤ 2 × 10^6。

感觉应该不是九老师出的题……要不然我这样的蒟蒻怎么A啊……
题目要让期望次数尽量多。因为在每个数不同的前提下，每一种状态出现的概率都是一样的，都是$\frac 1 {(n+m)!}$。但是要注意，并不是只有一种状态是排好序的。比如对于$1,2,3,3,5$来说，其实有两种状态都是排好序的！因为中间的$3$无论怎么轮换都是一样的。那么对于一个数列来说有多少种情况是排好序的呢？假设第$i$大的数的个数是$c_i$，不难发现答案是这个：
$$\sum{c_i!}$$
那么概率就是：
$$\frac{\sum{c_i!}}{(n+m)!}$$
期望最大概率最小，那么如何最小化$\sum{c_i!}$呢？
其实我们只需要贪心即可。
策略就是在$[l,r]$内每一次填$c_i$最小的那个数把它填起来。
这个过程只需要把$[l,r]$内的数拿出来排序就可以模拟了。
代码细节比较多，WA了一段时间。
```
#include<cstdio>
#include<algorithm>
#include<map>
#define LL long long
using namespace std;
const int maxn = 2e5 + 5;
const int maxm = 1e7 + 5;
const int B = 11000000;
const int mod = 998244353;
int n, m, l, r, N, tmp, T;
int num[maxn], lp, rp, ki[maxn], cnt, rest, mx;
LL step[maxm << 1], ans;

LL fpow(LL a, int b) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod, b >>= 1;
    }
    return ans;
}

void pre(int n) {
    step[0] = 1;
    for(register int i = 1; i <= n; ++i)
        step[i] = step[i - 1] * i % mod;
}

int main() {
    scanf("%d", &T);
    pre(B);
    while(T--) {
        scanf("%d%d%d%d", &n, &m, &l, &r);
        cnt = 0, N = n + m, ans = 1;
        for(register int i = 1; i <= n; ++i)
            scanf("%d", &num[i]);
        sort(num + 1, num + n + 1), num[n + 1] = 0;
        lp = lower_bound(num + 1, num + n + 1, l) - num;
        rp = upper_bound(num + 1, num + n + 1, r) - num - 1;
        for(register int i = lp; i <= rp; ++i) {
            if(num[i] != num[i - 1]) ki[++cnt] = 0;
            ++ki[cnt];
        }
        sort(ki + 1, ki + cnt + 1), ki[cnt + 1] = 0;
        rest = (r - l + 1 - cnt), mx = 0;
        tmp = 0;
        for(int i = 1; i <= cnt; ++i) {
            tmp = 0;
            while(ki[i] == ki[i + 1]) ++tmp, ++i;
            if(1ll * m < 1ll * rest * (ki[i] - ki[mx])) break;
            m -= rest * (ki[i] - ki[mx]), (rest += tmp + 1);
            mx = i;
        }
        int upcnt = m % rest, downh = ki[mx] + m / rest;
        ans = ans * fpow(step[downh], rest - upcnt) % mod;
        ans = ans * fpow(step[downh + 1], upcnt) % mod;
        for(register int i = mx + 1; i <= cnt; ++i)
            ans = ans * step[ki[i]] % mod;
        tmp = 0;
        for(register int i = 1; i <= lp; ++i) {
            if(num[i] != num[i - 1]) {
                ans = ans * step[tmp] % mod;
                tmp = 0;
            }
            ++tmp;
        }
        tmp = 0;
        for(register int i = rp + 1; i <= n + 1; ++i) {
            if(num[i] != num[i - 1]) {
                ans = ans * step[tmp] % mod;
                tmp = 0;
            }
            ++tmp;
        }
        printf("%lld\n", fpow(ans, mod - 2) * step[N] % mod);
    }
    return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链