传送门

全世界的题解都看不懂.jpg

题解写到一半莫名刷新结果全都白写了.jpg

首先要知道全概率公式(E(x)=sum_{i=0}^infty P(xgeq i))，证明如下

于是对于每一个(i)，我们只要计算出(P(ansgeq i))即可

然而因为这里要计算的是最小值，如果是大于等于很不方便，于是我们考虑转化为(P(ansgeq i)=1-P(ans<i))，也就是意味着每一个区间中都至少有一个数小于等于(i-1)

有一个性质，如果区间(a=[l1,r1])完全包含了区间(b=[l2,r2])，那么(a)是没有用的，因为(a)的最小值肯定小于等于(b)的最小值，对答案不可能有贡献。于是我们可以先把所有包含了其它区间的区间先去掉，再按左端点排一个序，那么右端点肯定也是递增的

考虑一个数，如果它小于等于(i-1)那么它会对一些区间产生贡献，且这些区间的编号肯定是连续的。我们把点和区间翻转，考虑用点去覆盖区间，那么现在的问题就变成了每个点能覆盖一些区间，且覆盖的概率为(p=frac{i-1}{x})，问所有区间都被覆盖的概率

设(l[i])为(i)能覆盖到的最左边的区间，(r[i])为最右边的区间，(f[i])为必选第(i)个点，且(r[i])及其之前的区间都被覆盖的概率，那么有$$f[i]=p(sum_{r[j]geq l[i]-1} f[j](1-p)^{i-j-1}+[l[i]=1]*(1-p)^{i-1})$$

就是说我们枚举上一个选的点(j)，那么必须有(r[j]geq l[i]-1)才能保证(r[i])及其之前的区间都被覆盖，又因为(j)是上一个被选的，所以([j+1,i-1])都没有被覆盖。

那么最后的答案就是(sum_{r[i]=m} f[i]*(1-p)^{n-i})，就是枚举最后一个被选的点，然后因为它是最后一个，所以([i+1,n])都没被覆盖

这个东西用双指针的话，可以优化到(O(n))

//minamoto
#include<bits/stdc++.h>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
int read(){
    int res,f=1;char ch;
    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);
    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');
    return res*f;
}
const int N=2005,mod=666623333;
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y%mod;}
int ksm(int a,int b){
    int res=1;
    for(;b;b>>=1,a=mul(a,a))if(b&1)res=mul(res,a);
    return res;
}
struct node{
    int l,r;
    inline bool operator <(const node &b)const
    {return l==b.l?r>b.r:l<b.l;}
}a[N];
int n,k,m,st[N],top,L[N],R[N],f[N],ans,invp[N];
int main(){
//	freopen("testdata.in","r",stdin);
    n=read(),k=read(),m=read();for(int i=1;i<=m;++i)a[i].l=read(),a[i].r=read();
    sort(a+1,a+1+m);
    for(int i=1;i<=m;++i){
        while(top&&a[i].r<=a[st[top]].r)--top;
        st[++top]=i;
    }
    m=top;for(int i=1;i<=m;++i)a[i]=a[st[i]];
    int h=1,t=0;
    for(int i=1;i<=n;++i){
        while(t<m&&a[t+1].l<=i)++t;
        while(h<=t&&a[h].r<i)++h;
        L[i]=h,R[i]=t;
    }
    for(int x=1;x<=k;++x){
        int sum,p,np,fp,leip,tot;
        sum=1,p=mul(dec(x,1),ksm(k,mod-2));
        np=dec(1,p),fp=ksm(np,mod-2);
        invp[0]=1,f[0]=1,leip=1;
        for(int i=1;i<=n;++i)invp[i]=mul(invp[i-1],fp);
        for(int i=1,j=0;i<=n;++i){
            while(j<i&&R[j]<L[i]-1)sum=dec(sum,mul(f[j],invp[j])),++j;
            f[i]=mul(sum,mul(leip,p)),leip=mul(leip,np);
            sum=add(sum,mul(f[i],invp[i]));
        }
        tot=0,leip=1;
        for(int i=n;i&&R[i]==m;--i,leip=mul(leip,np))tot=add(tot,mul(f[i],leip));
        ans=add(ans,dec(1,tot));
    }
    printf("%d
",ans);return 0;
}