[CF1295F] Good Contest

题目链接

Solution

【参考：官方题解，博客】

总体思路：计算出单调不升序列的数量，除以总数量 $\prod(R_i-L_i+1)$ 即是答案。

先把闭区间 $[L,R]$ 转换为左闭右开区间 $[L,R+1)$，然后离散化，即视所有 $L_i,R_i$ 把整个区间分成了 $O(n)$ 个小线段，离散化后的 $L_i,R_i$ 就指的是原来的 $L_i,R_i$ 是第几个小线段的端点。现在我们知道，一个单调不升序列一定是从右边的小线段往左边取值，即若 $i<j$，则 $i$ 所属小线段 $\geq$ $j$ 所属小线段。

欲 dp 解之：

• dp 状态：设 $dp[i][j]$ 表示前 $i$ 个数全在 $j$ 及其以后的小线段中，且后面的数全在第 $j$ 个小线段之前的方案数。

• 转移方程：考虑哪些数放在第 $j$ 个小线段中，即 $dp[i][j]$ 从 $dp[i-k][j+1]$ 转移而来，其中从 $i-k+1\sim i$ 的这 $k$ 个数全放在第 $j$ 个小线段。这样放的方案数是多少？注意到我们这 $k$ 个数必须从右往左放，一共有第 $j$ 个小线段的长度 $length(j)$ 那么多位置可以放。把问题抽象出来是：将 $k$ 个相同小球放入 $length(j)$ 个不同的盒子且允许盒子为空的方案数。这是一个经典的组合问题，其等价于在 $k$ 个小球之间插入 $length(j)-1$ 个隔板且隔板可以相邻，那么无论怎么插隔板，隔板和小球的总数是 $k+length(j)-1$，其中选 $k$ 个位置作为小球，一共是 $C_{k+length(j)-1}^k$ 种方案。

  综上，

  $$dp[i][j] = \sum\limits_{1\leq k\leq i\bigwedge j\in[L_{i-k+1},R_{i-k+1}]} dp[i-k][j+1]\cdot C_{k+length(j)-1}^k$$

  其中求和的条件 $j\in[L_{i-k+1},R_{i-k+1}]$ 是指 $i-k+1\sim i$ 这 $k$ 个数都能在第 $j$ 个线段里取值。

  注意上式只求了 $i-k+1\sim i$ 这 $k$ 个数全只在第 $j$ 个线段里取值的方案数，所以还要后缀和。

• 转移顺序：由方程可知，顺序枚举即可。

• 边界条件：$dp[0][j]=1$

复杂度：顺序枚举 $i,j,k$ 是 $O(n^3)$，求组合数 $O(n)$，共 $O(n^4)$.

Code

#include<algorithm>
#include<iostream>
#include<cstdio>

using namespace std;

typedef long long LL;

const LL MOD = 998244353;
const int N = 205;

LL fpow(LL bs, LL idx){
    LL res = 1;
    while(idx){
        if(idx & 1) (res *= bs) %= MOD;
        (bs *= bs) %= MOD;
        idx >>= 1;
    }
    return res;
}

int n, L[N], R[N], t[N];
LL dp[N][N], sum = 1;

inline LL C(LL x, LL y){
    if(y > x)   return 0ll;
    if(y == 0 || x == y)    return 1ll;
    LL res = 1, tmp = 1;
    for(LL i = x; i >= x - y + 1; i--)  (res *= i) %= MOD;
    for(LL i = 1; i <= y; i++)  (tmp *= i) %= MOD;
    return res * fpow(tmp, MOD - 2) % MOD;
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &L[i], &R[i]);
        (sum *= (R[i] - L[i] + 1)) %= MOD;
        t[++t[0]] = L[i], t[++t[0]] = R[i] + 1;
    }
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= n; i++){
        L[i] = lower_bound(t+1, t+t[0]+1, L[i]) - t;
        R[i] = lower_bound(t+1, t+t[0]+1, R[i] + 1) - t;
    }
    for(int j = 1; j <= t[0]; j++)  dp[0][j] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = L[i]; j < R[i]; j++){
            for(int k = 1; k <= i; k++){
                if(L[i-k+1] > j || R[i-k+1] <= j)   break;
                (dp[i][j] += dp[i-k][j+1] * C(t[j+1] - t[j] + k - 1, k) % MOD) %= MOD;
            }
        }
        for(int j = t[0] - 1; j >= 1; j--)  (dp[i][j] += dp[i][j+1]) %= MOD;
    }
    printf("%lld\n", dp[n][1] * fpow(sum, MOD - 2) % MOD);
    return 0;
}