题解：CF2125D Segments Covering

BGM114514 · 2025-07-23 22:04:00 · 题解

蒟蒻首次过 D，鸡冻得内牛满面嘤嘤嘤(╥╯^╰╥)……

题意简述

给你 n 条线段，每条线段都有其出现的概率，问 1 到 m 这个区间每个整点恰好被这些线段覆盖一次的概率。

Solution

看到概率，果断考虑 O(n) 概率 dp。

状态很容易想，dp_i 表示从 1 到 i 这个区间每个点恰好被覆盖一次的概率，那么答案就是 dp_m 了。

怎么转移呢？设 vector 数组 id_r 表示以 r 为右端点的所有线段的编号，计算 dp_i 时遍历 id_i，设当前遍历到的线段编号为 st，且存储线段的数组为 seg，那么 seg[st].r（即线段右端点）=i，dp_i 可从 dp_{seg[st].l-1}（即线段左端点前面）转移过来。

具体地，

其中 pp 表示与当前线段存在重叠的线段不出现的概率之积。

初始状态为 dp_0=1。

那么，怎么快速求 pp 呢？

我们设 sum_i 为右端点坐标 \ge i 的线段不出现的概率之积，容易发现

可以把 sum_i 当成前缀积来理解，反正这个可以预处理出来。

至于运算问题嘛，其实是可以直接乘逆元的，但由于懒得写我太菜，所以实现了一个分数类。（不要喷我啊嘤嘤嘤……）

最后再提醒一下，如果您也写了分数类，一定要注意在运算时给分子分母取模，我两发罚时就这么来的。（卧倒.jpg）

UPD：线段最短点前面的 -1 打成 -2 了呜呜呜，所以又交了一次，请求管理员给过。

Code

代码实现和思路中的变量名有所不同，请注意区分。

#include<bits/stdc++.h>
#define int long long
#define I using
#define AK namespace
#define IOI std

I AK IOI;

const int mod=998244353;
struct frac{
    int x,y;
    frac():x(0),y(1){}
    frac(int xx,int yy):x(xx),y(yy){}
    frac operator+(const frac& tmp){//加法 
        int m=y*tmp.y%mod;
        frac res;
        res.y=m,res.x=(x*tmp.y+tmp.x*y)%mod;//一定要取模啊！！！ 
        return res;
    }
    frac operator*(const frac& tmp){//乘法 
        frac res;
        res.y=y*tmp.y%mod,res.x=x*tmp.x%mod;//同上上 
        return res;
    }
    frac rev()const{//取倒数（给除法用） 
        return frac(y,x);
    } 
    frac operator/(const frac& tmp){
        frac res=tmp.rev();
        return *this*res;//*this 其实就是这个对象自己啦 
    }
    frac roll()const{//1-这个分数（用来求线段不出现的概率） 
        return frac(y-x,y);
    }
};
struct Segment{//存储线段 
    int l,r;
    frac p;
}seg[200005];
int n,m;
vector<int> id[200005];//存储右端点为 i 的线段编号 
frac dp[200005],sum[200005];//前缀积 
int qpow(int a,int b){//快速幂 
    if(b==0)return 1;
    int k=qpow(a,b>>1);
    k=k*k%mod;
    if(b&1)k=k*a%mod;
    return k;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<=m;i++)sum[i]=frac(1,1);//预处理 
    for(int i=1;i<=n;i++){
        int l,r,p,q;
        cin>>l>>r>>p>>q;
        seg[i].l=l,seg[i].r=r,seg[i].p=frac(p,q);
        id[r].push_back(i);
        sum[r]=sum[r]*frac(q-p,q);//预处理 
    }
    for(int i=1;i<=m;i++)sum[i]=sum[i]*sum[i-1];//同上 
    dp[0]=frac(1,1);//初始状态 
    for(int i=1;i<=m;i++){
        frac pro(1,1);
        for(int st:id[i]){//转移 
            int ll=seg[st].l,rr=seg[st].r;
            frac pp=seg[st].p;//表示当前线段出现的概率！！！不是 Solution 中说的乘积！！！ 
            dp[i]=dp[i]+pp*dp[ll-1]*sum[rr]/sum[ll-1]/pp.roll();//转移（注意区分变量名） 
        }
    }
    cout<<dp[m].x*qpow(dp[m].y,mod-2)%mod<<endl;//费马小定理求逆元 
    return 0;
}