P5469 [NOI2019] 机器人

· · 个人记录

神而明之，存乎其人。——题记

题意

数据范围

\begin{cases}n\leqslant 300,B[i]\leqslant 1e4(50\ pts)\\ n\leqslant 50,A[i]=1,B[i]=1e9(another\ 10\ pts)\\n\leqslant 300,B[i]\leqslant 1e9(100\ pts)\end{cases}

解析

0.题意分析

1.dp 设计

2.dp 优化

示范代码

#include<bits/stdc++.h>
#define il inline
#define re register
#define b_s basic_string
#define For(i,a,b) for(re int i=(a);i<=(b);++i)
#define foR(i,a,b) for(re int i=(a);i>=(b);--i)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
using namespace std;
il void rd(int &x){
    x=0;bool f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=0;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    x=f?x:-x;
    return;
}

const int maxn=307,maxm=2608;//maxm是最大区间数
const ll mod=1e9+7;
int n;
int A[307],B[307];

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

int id[maxn][maxn],toti;//0就是区间不存在 
il bool ok(int l,int mid,int r){return abs((mid-l)-(r-mid))<=2;}
il void sinte(int l,int r){//本函数是用于区间初始化的递归函数。 
    if(id[l][r]) return;
    id[l][r]=++toti;
    if(l>=r) return;
    For(mid,l,r)
        if(ok(l,mid,r))
            sinte(l,mid-1),sinte(mid+1,r);
}

int key[607],totk;
ll invfact[307];
int usek;
il void init(){//本函数负责读入，并参与到区间初始化和拉插初始化中。
    rd(n); usek=n+1;
    For(i,1,n){
        rd(A[i],B[i]);
        key[++totk]=A[i],key[++totk]=B[i]+1;//A[i]是到这里就变，B[i]是下一个才变。我们希望key里面存的每一个都是变的点，这样一来我们就可以取出左闭右开区间。 
    }
    sort(key+1,key+1+totk);
    totk=unique(key+1,key+1+totk)-key-1;//去重后结果。 

    sinte(1,n);

    invfact[0]=1;
    For(i,1,usek) invfact[i]=invfact[i-1]*inv(i)%mod;
}

int L,R,S,N;//当前考虑的闭区间的左右端点，该区间长度，计划中要dp出的长度 
ll dp[maxn][maxm]; bitset<maxm> vis;//该区间是否在本轮dp中访问过 
//dp[mx][now]表示第now个区间的最大值不超过mx的方案数。定义tp[mx][now]表示恰好为的方案数。
//对于非初始区间(r>l): 
//因为我们在dfs内实际上是逐个区间转移，我们可以先这样转移：dp(实为tp)[mx][now]=∑mid [ (∑i=0~mx tp[i][left])*(∑i=0~mx-1 tp[i][right]) ]=∑mid (dp[mx][left]*dp[mx-1][right]) 
//然后我们对dp前缀和，因为dp[mx][now]=∑i=1~mx tp[i][now]。不用关心i=0，因为对于非初始区间那里一定是0(A[i]>=1)(更实质地，只有虚区间会用到那个) 
il void dfs(int l,int r){
    re int now=id[l][r]; if(vis[now]) return; vis[now]=1;
    if(l>r){
        For(i,0,N) 
            dp[i][now]=1; 
        return;
    }
    if(l==r){
        if(A[l]<=L && R<=B[l])
            For(i,1,N) 
                dp[i][now]=1;
    }
    if(l<r){
        For(mid,l,r)
            if(ok(l,mid,r)){
                dfs(l,mid-1); dfs(mid+1,r);
                if(A[mid]<=L && R<=B[mid])
                    For(i,1,N) 
                        dp[i][now]=(dp[i][now] + dp[i][id[l][mid-1]] * dp[i-1][id[mid+1][r]]) % mod;
            }
    }
    For(i,1,N){
        dp[i][now]=dp[i-1][now]+dp[i][now];
        if(dp[i][now]>=mod) dp[i][now]-=mod;
    }
    return;
}

ll son[maxn],sonqian[maxn],sonhou[maxn];
ll mu[maxn],invmu[maxn];
il void work(){
    for(re int i=1;i<totk;++i){
        L=key[i],R=key[i+1]-1,S=R-L+1;
        if(S<=usek){
            N=S;
            dfs(1,n);
            For(i,1,toti) dp[0][i]=dp[N][i];//每次都把上一段的结果放在0处，此时的1就代表L，相当于平移了整个dp数组 
        }
        else{
            N=usek;
            dfs(1,n);
            //首先我们处理分子 son 及其前后缀积。  拉插的代入值 x 应当为区间末端 R 。 
            sonqian[0]=sonhou[usek+1]=1; 
            For(j,1,usek){//因为这里1代表L，所以rj(j为1~usek的任意值)=j+L-1
                son[j]=S-j;//实际的式子是son[j]=R-rj=R-L+1-j=S-j，由else知S>usek>=j，所以不用判负，而且 R<=1e9 ，所以也不用模 
                sonqian[j]=sonqian[j-1]*son[j]%mod;
            }
            foR(j,usek,1) sonhou[j]=sonhou[j+1]*son[j]%mod;

            //然后我们来处理分母
            For(i,1,usek){
                if(((usek-i)&1)==0) invmu[i]=invfact[i-1]*invfact[usek-i]%mod;
                else invmu[i]=mod-invfact[i-1]*invfact[usek-i]%mod;
            } 

            for(re int i=1;i<=usek;++i){
                ll fenzi=sonqian[i-1]*sonhou[i+1]%mod;
                ll xishu=fenzi*invmu[i]%mod;
                For(now,1,toti)//暂时放在这里
                    dp[N+1][now]=(dp[N+1][now]+xishu*dp[i][now])%mod;
            }

            For(now,1,toti) dp[0][now]=dp[N+1][now],dp[N+1][now]=0;
        }
        vis.reset();
        For(i,1,N)
            For(j,1,toti)
                dp[i][j]=0;//清空dp。
    }
}

int main(){
    init();
    work();
    wt(dp[0][1]);
    return 0;
}

总结与反思

1.知识点

2.解题中的失误

3.其他

后记