P3600 隨機數生成器

sol

期望不太方便，轉計數。那么就是要求對每個值，最后結果恰為這個值的方案數。

恰好不太好求，考慮差分，轉化為至多，那么就是要對每個值求答案不超過這個值的方案數。

要求所有區間區間內最小值的最大值不超過標準值，也就是要求每個區間都得有一個不超過標準值的數。容易將原序列轉化為 0-1 序列，再轉化為線段覆蓋問題：要求放一些點點，使得每個給出的區間內都包含有一個點。求放點方案數。

首先不難發現不存在包含關系的區間，因為小區間滿足大區間必然滿足。那么現在區間右端點關于左端點不降。

考慮 DP 求這個，設計 \(f(i,j)\) 表示前 \(i\) 個點共選了 \(j\) 個點且欽定選第 \(i\) 個點使得所有左端點不超過 \(i\) 的區間均滿足性質的方案數。轉移考慮枚舉上一個合法點的位置，那么簡單預處理出覆蓋各個點的最左的區間與最右的區間，則上一個合法點必須位于當前點前最后一個不被當前點覆蓋的區間內。這個顯然可以簡單前綴和優化。

求出 \(f\) 之后找方案數是簡單的，枚舉標準值 \(v\) 與總放點數 \(i\)，有系數 \(i^v(n-i)^{x-v}\)，意義顯然。最后枚舉答案差分得到方案并除總方案數得到期望即可。

code

const int N=2005;

int n,x,q,m;
struct node{int l,r;}ns[N],ls[N];
int lb[N],rb[N];

int dtl[N<<2],dtr[N<<2],lzl[N<<2],lzr[N<<2];
void build(int x=1,int l=1,int r=n){
    dtl[x]=lzl[x]=inf;
    dtr[x]=lzr[x]=-inf;
    if(l==r)return;
    int m=l+r>>1;
    build(x<<1,l,m);
    build(x<<1|1,m+1,r);
}
void pushdown(int x){
    chmin(dtl[x<<1],lzl[x]);
    chmin(dtl[x<<1|1],lzl[x]);
    chmin(lzl[x<<1],lzl[x]);
    chmin(lzl[x<<1|1],lzl[x]);
    chmax(dtr[x<<1],lzr[x]);
    chmax(dtr[x<<1|1],lzr[x]);
    chmax(lzr[x<<1],lzr[x]);
    chmax(lzr[x<<1|1],lzr[x]);
    lzl[x]=inf,lzr[x]=-inf;
}
void modify(int lq,int rq,int v,int x=1,int l=1,int r=n){
    if(lq<=l&&r<=rq)return chmin(dtl[x],v),chmin(lzl[x],v),chmax(dtr[x],v),chmax(lzr[x],v),void();
    int m=l+r>>1;
    pushdown(x);
    if(lq<=m)modify(lq,rq,v,x<<1,l,m);
    if(m<rq)modify(lq,rq,v,x<<1|1,m+1,r);
}
pii query(int k,int x=1,int l=1,int r=n){
    if(l==r)return {dtl[x],dtr[x]};
    int m=l+r>>1;
    pushdown(x);
    if(k<=m)return query(k,x<<1,l,m);
    else return query(k,x<<1|1,m+1,r);
}

mint f[N][N],s[N][N];
mint g[N],ans;

inline void Main(){
    cin>>n>>x>>q;
    rep(i,1,q)cin>>ns[i].l>>ns[i].r;
    sort(ns+1,ns+1+q,[&](node a,node b){if(a.l!=b.l)return a.l<b.l;return a.r<b.r;});
    int mx=inf;
    per(i,q,1)if(ns[i].r<mx)mx=ns[i].r,ls[++m]=ns[i];
    reverse(ls+1,ls+1+m);
    build();
    rep(i,1,m)modify(ls[i].l,ls[i].r,i);
    rep(i,1,n){
        pii res=query(i);
        if(res.fir!=inf)lb[i]=res.fir,rb[i]=res.sec;
        else rb[i]=rb[i-1],lb[i]=rb[i]+1;
    }
    f[0][0]=s[0][0]=1;
    rep(i,1,n)s[i][0]+=s[i-1][0];
    rep(j,1,n){
        rep(i,j,n){
            f[i][j]=s[i-1][j-1]-(ls[lb[i]-1].l-1<0?0:s[ls[lb[i]-1].l-1][j-1]);
            s[i][j]+=f[i][j];
        }
        rep(i,1,n)s[i][j]+=s[i-1][j];
    }
    rep(v,1,x)rep(i,1,n)g[v]+=(s[n][i]-s[ls[m].l-1][i])*qpow(v,i)*qpow(x-v,n-i);
    rep(v,1,x)ans+=v*(g[v]-g[v-1]);
    put(ans/qpow(x,n));
}