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

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

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

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

然而因为这里要计算的是最小值，如果是大于等于很不方便，于是我们考虑转化为\(P(ans\geq 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
    
     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
     
      inline bool cmax(T&a,const T&b){return a
      
       '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