题解：CF303E Random Ranking

ssy666666 · 2026-07-23 18:13:03 · 题解

模拟赛考到，也是顺利爆零了好吧。

符号定义

• 定义一个人 u 的分数段为 [l_u,r_u]（和题目的定义相同）。
• 定义 len_u=r_u-l_u。
• 定义 p \rightarrow q 表示 p 给 q 做贡献，你可以理解为 c++ 语句 q += p。

还有的定义会在后文具体给出。

正确解法

首先，我们先考虑弱化版问题。假如所有的 n 个选手的分数区间相同，那么概率是多少？

显然这 n 个选手是在公平竞争，那么概率获得任何名次的概率都是 \frac{1}{n}。

我们发现公平竞争是好做的，因此我们考虑划分若干个分数段，这样在这些分数段内全都是公平竞争，而 n 个人公平竞争。而我们要考虑的实际上还有在他们前面的有多少人。知道了这两个信息，必然能得到答案。

因此，我们考虑 dp。我们枚举当前选择哪个分数段，设其为 [L,R]，使得不存在任何一个人只包含 [L,R] 的一部分，即不存在 L \le l_i \le R 或 L \le r_i \le R，同时枚举计算第 u 个人的贡献。

接着，我们定义 dp_{i,j,k} 表示前 i 个人（不考虑第 u 个人），有 j 个人在 [L,R] 前，有 k 个人在 [L,R] 这一段内。

因此，对于新的一个人 i+1，定义他的分数区间为 [l_{i+1},r_{i+1}]，定义 len_{i+1} = r_{i+1} - l_{i+1}，我们进行分类讨论：

• 如果该区间在 [L,R] 左侧，即 r_{i+1} \le L，那么显然有：

• 如果该区间在 [L,R] 右侧，即 l_{i+1} \ge R，那么显然有：

• 反之，该区间一定会包含 [L,R]，那么考虑这个人分数会落到哪个区间：

1. 若落到 [l_{i+1},L]，概率为 \frac{L - l_{i+1}}{len_{i+1}}，那么有：

2. 若落到 [L,R]，概率为 \frac{R-L}{len_{i+1}}，那么有：

3. 若落到 [R,r_{i+1}]，概率为 \frac{r_{i+1}-R}{len_{i+1}}，那么有：

初始化 dp_{0,0,0}=1，其他全为 0 即可，时间复杂度 O(n^5)，已经能通过这道题。

但是这个做法显然还能够优化。我们发现，每次 dp 的过程非常相似，具体的，就只有一个人不同。那我们能不能整体 dp 一次，再把这个人的贡献刨掉呢？事实证明，这是可以的。

我们现在考虑，我们已经得到了 dp_{n,j,k}(1 \le j,k,j+k \le n) 的值，并且不刨除任何人。而我们当前想刨除掉第 u 个人，得到一个新的数组 f_{j,k} 表示刨除 u 后，在该段前面有 j 个人，在该段中有 k 个人的概率。

先做一个剪枝：如果 r_u \le L 或者 l_u \ge R，显然该段不会对 u 产生任何的贡献。

设 u 的分数在这一段前的概率为 P_f = \frac{L - l_u}{len_u}，在这一段中的概率为 P_m=\frac{R-L}{len_u}，在这一段后的概率为 P_b=\frac{r_u-R}{len_u}，因此我们可以写出关系式：

换而言之，对 u 有贡献的段一定满足 l_u \le L \le R \le r_u。

因此，由于 R-L \ne 0，故必然有 P_m \ne 0。因此移项可得：

将 k-1 变为 k 可得：

正序枚举 j，倒序枚举 k 即可。时间复杂度 O(n^4)。本文提到的做法只是一种，强烈推荐读者再手推一遍，即使和我的不一样也可能是正确的。

AC Code

为了放抄袭，我直接放我模拟赛补题的代码，里面维护的是对 10^9 + 9 取模后的结果。如果你不放心可以手动验证。

#include<bits/stdc++.h>
#define int long long
using namespace std ;
const int MAXN = 250 ;
const int MOD = 1e9 + 9 ;

int ksm(int i , int j) {
    int ans = 1 ;
    while (j) {
        if (j & 1) {
            ans = ans * i % MOD ;
        }
        i = i * i % MOD ;
        j >>= 1 ;
    }
    return ans ;
}

int dp[MAXN][MAXN][MAXN] ;
int l[MAXN] , r[MAXN] ;
int num[MAXN] ;

int ans[MAXN][MAXN] ;

int f[MAXN][MAXN] ;

int val[MAXN] ;
int inv[MAXN] ;
signed main()
{
//  freopen("q.in" , "r" , stdin) ;
//  freopen("q.out" , "w" , stdout) ;

    ios::sync_with_stdio(0) ;
    cin.tie(0) ;
    cout.tie(0) ;

    int n ;
    cin >> n ;

    val[0] = 1 ;
    for (int i = 1 ; i <= n ; i ++) {
        val[i] = val[i - 1] * i % MOD ;
    }
    inv[n] = ksm(val[n] , MOD - 2) ;
    for (int i = n - 1 ; i >= 0 ; i --) {
        inv[i] = inv[i + 1] * (i + 1) % MOD ;
    }

    for (int i = 1 ; i <= n ; i ++) {
        inv[i] = inv[i] * val[i - 1] % MOD ;
    }

    for (int i = 1 ; i <= n ; i ++) {
        cin >> l[i] >> r[i] ;
        num[2 * i - 1] = l[i] ;
        num[2 * i] = r[i] ;
    }
    sort (num + 1 , num + 1 + 2 * n) ;
    int len = unique(num + 1 , num + 1 + 2 * n) - num - 1 ;

    dp[0][0][0] = 1 ;
    for (int e = 1 ; e <= len - 1 ; e ++) {
        for (int i = 1 ; i <= n ; i ++) {
            int INV = ksm(r[i] - l[i] , MOD - 2) ;
            for (int j = 0 ; j <= i ; j ++) {
                for (int k = 0 ; k <= i - j ; k ++) {
                    dp[i][j][k] = 0 ;

                    if (r[i] <= num[e]) {   //在左边
                        if (j != 0)
                            dp[i][j][k] = dp[i - 1][j - 1][k] ;
                        else
                            dp[i][j][k] = 0 ;
                    }

                    else if (l[i] >= num[e + 1]) {  //在右边
                        if (i - j - k != 0) {
                            dp[i][j][k] = dp[i - 1][j][k] ;
                        }
                        else {
                            dp[i][j][k] = 0 ;
                        }
                    }

                    else {
                        int len1 = max(num[e] - l[i] , 0ll) ;   //左侧的长度
                        int len2 = num[e + 1] - num[e] ;        //枚举的区间长度
                        int len3 = max(r[i] - num[e + 1] , 0ll) ;   //右侧长度

                        if (j != 0)
                            dp[i][j][k] += dp[i - 1][j - 1][k] * len1 % MOD * INV ;

                        if (k != 0)
                            dp[i][j][k] += dp[i - 1][j][k - 1] * len2 % MOD * INV ;

                        if (i - j - k != 0)
                            dp[i][j][k] += dp[i - 1][j][k] * len3 % MOD * INV ;

                        dp[i][j][k] %= MOD ;
                    }
                }
            }
        }

        for (int i = 1 ; i <= n ; i ++) {
            int INV = ksm(r[i] - l[i] , MOD - 2) ;
            int INV2 = ksm(num[e + 1] - num[e] , MOD - 2) ;

            if (r[i] <= num[e]) {       //左侧
                continue ;
            }

            else if (l[i] >= num[e + 1]) {  //右侧 
                continue ;
            }

            else {
                for (int j = 0 ; j <= n ; j ++) {
                    for (int k = 0 ; k <= n ; k ++) {
                        f[j][k] = 0 ;
                    }
                }
                int len1 = max(num[e] - l[i] , 0ll) ;   //同理
                int len2 = num[e + 1] - num[e] ;
                int len3 = max(r[i] - num[e + 1] , 0ll) ;

                for (int j = 0 ; j < n ; j ++) {
                    for (int k = n - j - 1 ; k >= 0 ; k --) {
                        f[j][k] = dp[n][j][k + 1] - f[j][k + 1] * len3 % MOD * INV % MOD - (j > 0 ? f[j - 1][k + 1] : 0) * len1 % MOD * INV % MOD ;
                        f[j][k] = (f[j][k] + 2 * MOD) % MOD ;
                        f[j][k] = f[j][k] * (r[i] - l[i]) % MOD * INV2 % MOD ;
                    }
                }
            }

            for (int j = 0 ; j < n ; j ++) {
                for (int k = 0 ; k < n - j ; k ++) {
                    int g = inv[k + 1] ;
                    const int l = f[j][k] * INV % MOD * (num[e + 1] - num[e]) % MOD * g % MOD ;
                    ans[i][j + 1] += l ;
                    if (ans[i][j + 1] >= MOD)   ans[i][j + 1] -= MOD ;
                    ans[i][j + k + 2] += MOD - l ;
                    if (ans[i][j + k + 2] >= MOD)   ans[i][j + k + 2] -= MOD ;
                }
            }
        }
    }

    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            ans[i][j] += ans[i][j - 1] ;
            if (ans[i][j] >= MOD)   ans[i][j] -= MOD ;
        }
    }

    for (int i = 1 ; i <= n ; i ++) {
        for (int j = 1 ; j <= n ; j ++) {
            cout << ans[i][j] << " " ;
        }
        cout << "\n" ;
    }
    return 0 ;
}