[题解] CF1295F Good Contest

首先把题目所求的概率变成合法方案数除以总方案数，所以这题就变成了一个计数问题

发现值域很大，但是 n 很小，考虑把区间化成左闭右开的形式然后离散化

记所有端点排好序之后为 b_1, b_2\dots,b_q，b_{q+1}=b_q+1，这些端点把值域分成 [b_1,b_2),[b_2,b_3),\dots,[b_q,b_{q+1}) 这 q 段区间

为了设定边界，[b_q,b_{q+1}) 中强制放一个 0 号区间

设 f_{i,j} 表示前 i 个数不增，第 i 个数在第 j 段区间的方案数

设枚举第 j 段区间放了 k 个数，考虑枚举 k，则方案数为 \binom {b_{j+1}-b_j+i-k-1}{i-k}

那么有转移方程 f_{i,j}=\sum\limits_{k<i}\binom {b_{j+1}-b_j+i-k-1}{i-k}\sum\limits_{t>j}f_{k,t}

注意在枚举 k 的时候判断一下是否 k+1,\dots ,i 中的所有区间都包含第 j 段区间

总方案数即为所有区间长的乘积

时间复杂度 \mathcal O(n^4)

code:

#include<bits/stdc++.h>
#define MAXN 110
#define p 998244353
#define int long long
using namespace std;
int n,l[MAXN],r[MAXN],s[MAXN];
int b[MAXN],tot;
int qpow(int x,int y){
    int ret=1;
    for(;y;y>>=1,x=x*x%p)if(y&1)ret=ret*x%p;
    return ret;
}
int C(int x,int y){
    int ret=1;
    for(int i=x;i>=x-y+1;i--)ret=ret*i%p;
    for(int i=y;i;i--)ret=ret*qpow(i,p-2)%p;
    return ret;
}
int f[MAXN][MAXN];
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&l[i],&r[i]);r[i]++;
        b[++tot]=l[i];b[++tot]=r[i];s[i]=r[i]-l[i];
    }sort(b+1,b+tot+1);tot=unique(b+1,b+tot+1)-b-1;
    for(int i=1;i<=n;i++){
        l[i]=lower_bound(b+1,b+tot+1,l[i])-b;
        r[i]=lower_bound(b+1,b+tot+1,r[i])-b;
    }
    f[0][tot]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<tot;j++)
            for(int k=i-1;k>=0;k--){
                if(!(l[k+1]<=j&&j+1<=r[k+1]))break;
                int now=0;
                for(int t=j+1;t<=tot;t++)now=(now+f[k][t])%p;
                now=now*C(b[j+1]-b[j]-1+i-k,i-k)%p;
                f[i][j]=(f[i][j]+now)%p;
            }
    int ans=0;
    for(int i=1;i<tot;i++)ans=(ans+f[n][i])%p;
    for(int i=1;i<=n;i++)ans=ans*qpow(s[i],p-2)%p;
    printf("%lld",ans);
    return 0;
}