P3600 随机数生成器

· · 个人记录

霜风凄紧，关河冷落，残照当楼。——题记

题意

数据范围

解析

0.区间整理

1.转化题意

E(Ans)= \sum\limits_{i=1}^x P(Ans=i)* i =\dfrac {\sum\limits_{i=1}^x Cases(Ans=i)* i}{x^n}

2.设计 dp 状态

dp[i]=\sum\limits_{j\ that\ L[i]-R[j]\leqslant1\ and\ L[i]-R[j-1]>1}^{i-1} (dp[j]* (x-T)^{i-j-1})* T

3.dp 优化

4.再谈前缀和优化的枚举T一维 dp与本题的加强版

#include<bits/stdc++.h>
#define ll long long
#define us unsigned
#define b_s basic_string
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define foR(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
ll rd(){
    ll s=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){s=(s<<3)+(s<<1)+(ch^48);if(ch!='\n') ch=getchar();}
    return s*f;
}
char wtst[66];
int wtps;
void wt(ll x){
    if(x<0) putchar('-'),x=-x;
    while(x>9) wtst[++wtps]=(x%10+'0'),x/=10;
    wtst[++wtps]=x+'0';
    while(wtps) putchar(wtst[wtps--]);
    return;
}
void wth(ll x){wt(x);putchar('\n');return;}
void wtk(ll x){wt(x);putchar(' ');return;}

const int maxn=2e3+7,mod=666623333;
int n,x,q,cnt,L[maxn],R[maxn],to[maxn];
bool fei[maxn];
struct space{
    int l,r;
}a[maxn],u[maxn];
bool cmpsp(space x,space y){return x.l!=y.l?x.l<y.l:x.r<y.r;}
int tp[maxn][maxn],dp[maxn][maxn],res[maxn],ans[maxn],rans[maxn],ANS;

void pre(){
    n=rd(),x=rd(),q=rd();
    For(i,1,q) a[i].l=rd(),a[i].r=rd();

    //去除包含其他区间的区间,并保证区间有序性
    sort(a+1,a+1+q,cmpsp);

//      int p=1,ln=a[1].l,rn=a[1].r;
//      For(i,2,q){
//          if(a[i].l<=ln && a[i].r>=rn) fei[i]=1;
//          else if(a[i].l>=ln && a[i].r<=rn) fei[p]=1,p=i,ln=a[i].l,rn=a[i].r;
//          else p=i,ln=a[i].l,rn=a[i].r;
//      }//bug 1,效果是不能正确地删掉区间
         //(反例:[1,7] [2,8] [3,4]  上面那种做法会bug (ln=1,rn=7->ln=2,rn=8->删掉[2,8]并且ln=3,rn=4,但不会继续回溯删掉[1,7])) 

    for(int i=1;i<=q;i++){
        for(int j=1;j<=q;j++){
            if(i!=j){
                if(a[i].l==a[j].l&&a[i].r==a[j].r&&(fei[i]==1||fei[j]==1)) continue;
                if(a[i].l<=a[j].l&&a[i].r>=a[j].r){
                    fei[i]=1;
                }
            }
        }
    }
    For(i,1,q)
        if(!fei[i])
            ++cnt,u[cnt].l=a[i].l,u[cnt].r=a[i].r;

    //处理L与R
    int LN=1,RN=0;
    For(i,1,n){
        while(LN<=cnt && u[LN].r<i) ++LN;//bug 2(<=cnt),效果是使得在最右一个区间右边的点的L趋于无穷大以至于无法向那些点转移(有理由认为这本来应当造成越界访问...) 
                                         //注意必须是<=cnt而非+1<=cnt,因为L随右,它们的L是那个不存在的"cnt+1" 
        while(RN+1<=cnt && u[RN+1].l<=i) ++RN;
        L[i]=LN,R[i]=RN;
    }

    //处理转移的右端点 
    int ton=1;
    For(i,0,n-1){
        while(ton<=n+1 && R[i]+1>=L[ton]) ++ton;
        --ton;
        to[i]=ton;
    }
    to[n]=n+1;//bug 3,效果是dp[n][j]不断给tp[1][j+1]扔负数(因为to[n]=0) 

    return;
}

void DP(){
    dp[0][0]=1;//我们的DP数组是差分意义下的。只要保证每次转移以前他们已经被改成正常的就好 
    For(i,0,n)
        For(j,0,i){
            if(i>0) tp[i][j]=(tp[i][j]+tp[i-1][j])%mod;
            dp[i][j]=(dp[i][j]+tp[i][j])%mod;
            tp[i+1][j+1]=((ll)tp[i+1][j+1]+dp[i][j])%mod;
            tp[to[i]+1][j+1]=((ll)tp[to[i]+1][j+1]-dp[i][j]+mod)%mod;
        }

    For(j,1,n)
        foR(i,n,0){//u[cnt].l,u[cnt].r) //bug 4,效果是在最右一个区间右边还有点的时候在统计res[j]时忽略那些点 
            if(R[i]<cnt) break;
            res[j]=((ll)res[j]+dp[i][j])%mod;//res:放j个的实际方案数
        }
    return;
}

int qpow(int x,int t){
    int ret=1;
    while(t){
        if(t&1) ret=(ll)ret*x%mod;
        x=(ll)x*x%mod;
        t>>=1;
    }
    return ret;
}

int inv(int x){return qpow(x,mod-2);}

void sol(){
    For(T,1,x){
        For(j,1,n)
            ans[T]=((ll)ans[T]+(ll)res[j]*qpow(T,j)%mod*qpow(x-T,n-j)%mod)%mod;//ans:<=T的实际方案数 
        rans[T]=((ll)ans[T]-ans[T-1]+mod)%mod;//rans:==T的实际方案数 
        ANS=((ll)ANS+(ll)rans[T]*T%mod)%mod;//ANS:总期望之和 
    }
    ANS=(ll)ANS*inv(qpow(x,n))%mod;//ANS在这里就变成全期望/全组合=真期望了 
    wt(ANS);
}

int main(){
    pre();
    DP();
    sol();
    return 0;
}

总结与反思

1.知识点

2.解题中的失误

3.其他

后记