devbox
思考机器5
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

P5469 [NOI2019] 机器人 洛谷黑题题解

作者：思考机器5 | 2024-01-29 18:35:18

赞

踩

P5469 [NOI2019] 机器人 洛谷黑题题解

[NOI2019] 机器人

题目背景

时限 3 秒，内存 512MB

题目描述

小 R 喜欢研究机器人。

最近，小 R 新研制出了两种机器人，分别是 P 型机器人和 Q 型机器人。现在他要测试这两种机器人的移动能力，测试在从左到右排成一排的 n n n 个柱子上进行，柱子用 1 − n 1 - n 1−n 依次编号， i i i 号柱子的高度为一个正整数 h i h_i hi​。机器人只能在相邻柱子间移动，即：若机器人当前在 i i i 号柱子上，它只能尝试移动到 i − 1 i - 1 i−1 号和 i + 1 i + 1 i+1 号柱子上。

每次测试，小 R 会选取一个起点 s s s，并将两种机器人均放置在 s s s 号柱子上。随后它们会按自己的规则移动。

P 型机器人会一直向左移动，但它无法移动到比起点 s s s 更高的柱子上。更具体地，P 型机器人在 l ( l ≤ s ) l (l \leq s) l(l≤s) 号柱子停止移动，当且仅当下列两个条件均成立：

  • l = 1 l = 1 l=1 或 h l − 1 > h s h_{l-1} > hs hl−1​>hs。

  • 对于满足 l ≤ j ≤ s l \leq j \leq s l≤j≤s 的 j j j，有 h j ≤ h s h_j \leq h_s hj​≤hs​。

Q 型机器人会一直向右移动，但它只能移动到比起点 s s s 更低的柱子上。更具体地，Q 型机器人在 r ( r ≥ s ) r (r \geq s) r(r≥s) 号柱子停止移动，当且仅当下列两个条件均成立：

  • r = n r = n r=n 或 h r + 1 ≥ h s h_{r+1} \geq h_s hr+1​≥hs​。

  • 对于满足 s < j ≤ r s < j \leq r s<j≤r 的 j j j，有 h j < h s h_j < h_s hj​<hs​。

现在，小 R 可以设置每根柱子的高度， i i i 号柱子可选择的高度范围为 [ A i , B i ] [A_i, B_i] [Ai​,Bi​]，即 A i ≤ h i ≤ B i A_i \leq h_i \leq B_i Ai​≤hi​≤Bi​。小 R 希望无论测试的起点 s s s 选在哪里，两种机器人移动过的柱子数量的差的绝对值都小于等于 2 2 2。他想知道有多少种柱子高度的设置方案满足要求，小 R 认为两种方案不同当且仅当存在一个 k k k，使得两种方案中 k k k 号柱子的高度不同。请你告诉他满足要求的方案数模 1 0 9 + 7 10^9 + 7 109+7 后的结果。

输入格式

第一行一个正整数 n n n，表示柱子的数量。

接下来 n n n 行，第 i i i 行两个正整数 A i , B i A_i, B_i Ai​,Bi​，分别表示 i i i 号柱子的最小和最大高度。

输出格式

仅一行一个整数，表示答案模 1 0 9 + 7 10^9 + 7 109+7 的值。

样例 #1

样例输入 #1

5
3 3
3 3
3 4
2 2
3 3

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

样例输出 #1

1

  • 1

提示

更多样例

您可以通过附加文件获得更多样例。

样例 2

见附加文件的 robot/robot2.in 与 robot/robot2.ans。

样例 3

见附加文件的 robot/robot3.in 与 robot/robot3.ans。

样例 4

见附加文件的 robot/robot4.in 与 robot/robot4.ans。

样例 1 解释

柱子高度共两种情况：

  • 高度为：3 2 3 2 3。此时若起点设置在 5 5 5，P 型机器人将停在 1 1 1 号柱子，共移动 4 4 4 个柱子。Q 型机器人停在 5 5 5 号柱子，共移动 0 0 0 个柱子，不符合条件。

  • 高度为：3 2 4 2 3。此时无论起点选在哪，都满足条件，具体见下表：

起点编号P 型机器人Q 型机器人
1 1 1停在 1 1 1 号柱子，移动过 0 0 0 个停在 2 2 2 号柱子，移动过 1 1 1 个
2 2 2停在 2 2 2 号柱子，移动过 0 0 0 个停在 2 2 2 号柱子，移动过 0 0 0 个
3 3 3停在 1 1 1 号柱子，移动过 2 2 2 个停在 5 5 5 号柱子，移动过 2 2 2 个
4 4 4停在 4 4 4 号柱子，移动过 0 0 0 个停在 4 4 4 号柱子，移动过 0 0 0 个
5 5 5停在 4 4 4 号柱子，移动过 1 1 1 个停在 5 5 5 号柱子，移动过 0 0 0 个

数据范围

对于所有测试数据： 1 ≤ n ≤ 300 1 \leq n \leq 300 1≤n≤300 , 1 ≤ A i ≤ B i ≤ 1 0 9 1 \leq A_i \leq B_i \leq 10^9 1≤Ai​≤Bi​≤109。

每个测试点的具体限制见下表：

测试点编号 n ≤ n\le n≤特殊性质
1 , 2 1,2 1,2 7 7 7 A i = B i , B i ≤ 7 A_i=B_i,B_i\le 7 Ai​=Bi​,Bi​≤7
3 , 4 3,4 3,4 7 7 7 B i ≤ 7 B_i\le 7 Bi​≤7
5 , 6 , 7 5,6,7 5,6,7 50 50 50 B i ≤ 100 B_i\le 100 Bi​≤100
8 , 9 , 10 8,9,10 8,9,10 300 300 300 B i ≤ 1 0 4 B_i\le 10^4 Bi​≤104
11 , 12 11,12 11,12 50 50 50 A i = 1 , B i = 1 0 9 A_i=1,B_i=10^9 Ai​=1,Bi​=109
13 , 14 , 15 13,14,15 13,14,15 50 50 50无
16 , 17 16,17 16,17 150 150 150无
18 , 19 18,19 18,19 200 200 200无
20 20 20 300 300 300无
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int res=0; bool f=0;
    char ch=getchar();
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) res=res*10+(ch^'0'),ch=getchar();
    return f?-res:res;
}
const int N=605,mod=1000000007;
struct node{
    int l,r;
    bool operator<(const node &t)const{return r-l<t.r-t.l;}
}p[3030];
int n,tot,id[N][N],a[N],b[N];
int fac[N],inv[N];
inline int qmi(int x,int y)
{
    int res=1;
    while(y)
    {
        if(y&1) res=1ll*res*x%mod;
        x=1ll*x*x%mod;
        y>>=1;
    }
    return res;
}
void init(int n)//预处理阶乘和逆元
{
    fac[0]=inv[0]=1;
    for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
    inv[n]=qmi(fac[n],mod-2);
    for(int i=n-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
}
inline void add(int &x,int y)
{
    x+=y;
    if(x>=mod) x-=mod;
}
void dfs(int l,int r)//预处理合法区间
{
    if(id[l][r]||l>r) return;
    id[l][r]=++tot;
    p[tot]={l,r};
    for(int i=l;i<=r;i++)//枚举分界线   
        if(abs((i-l)-(r-i))<=2)
            dfs(l,i-1),dfs(i+1,r);
}
int num[N],cnt;
void read_and_change()
{
    for(int i=1;i<=n;i++)
    {
        num[++cnt]=a[i]=read();
        num[++cnt]=b[i]=read()+1;//左闭右开 后面方便
    }
    sort(num+1,num+cnt+1);
    cnt=unique(num+1,num+cnt+1)-num-1;
    for(int i=1;i<=n;i++)
    {
        a[i]=lower_bound(num+1,num+cnt+1,a[i])-num;
        b[i]=lower_bound(num+1,num+cnt+1,b[i])-num;
    }
}
int f[3030][N],pre[N],suf[N];
inline void lag(int l,int r,int len)
{
    if(len<=n+1) 
    {
        for(int i=1;i<=tot;i++) f[i][0]=f[i][len];
        return;
    }
    for(int i=1;i<=tot;i++) f[i][0]=0;
    pre[0]=suf[n+2]=1;//pre、suf就是把带入len之后的式子的分子前后缀前
    for(int i=1;i<=n+1;i++) pre[i]=1ll*pre[i-1]*((len-i+mod)%mod)%mod;
    for(int i=n+1;i>=1;i--) suf[i]=1ll*suf[i+1]*((len-i+mod)%mod)%mod;
    for(int i=1;i<=n+1;i++)
    {
        int val=1ll*pre[i-1]*suf[i+1]%mod/*分子*/*inv[n+1-i]%mod*inv[i-1]%mod/*分母*/*(((n+1-i)&1)?mod-1:1)%mod/*分母的符号*/;
        for(int j=1;j<=tot;j++)
            add(f[j][0],1ll*val*f[j][i]%mod);
    }
}
int main()
{
    n=read();
    init(n+5);
    dfs(1,n); sort(p+1,p+tot+1);
    read_and_change();//读入并离散化
    for(int i=0;i<=n+1;i++) f[0][i]=1;
    for(int t=1;t<cnt;t++)
    {
        int len=min(n+1,num[t+1]-num[t]);
        for(int i=1;i<=tot;i++)
        {
            int l=p[i].l,r=p[i].r;
            for(int j=l;j<=r;j++)
                if(abs((j-l)-(r-j))<=2&&t>=a[j]&&t<b[j])
                    for(int k=1;k<=len;k++)
                        add(f[id[l][r]][k],1ll*f[id[l][j-1]][k]*f[id[j+1][r]][k-1]%mod);
                        //最初的DP中的“最大值”就是最靠右的最大值，所以右区间的最大值一定比k小(j位置是k)
            for(int k=1;k<=len;k++) 
                add(f[id[l][r]][k],f[id[l][r]][k-1]);//前缀和优化
        }
        lag(num[t],num[t+1],num[t+1]-num[t]);
        for(int i=1;i<=tot;i++)
            for(int j=1;j<=len;j++)
                f[i][j]=0;
    }
    printf("%d\n",f[id[1][n]][0]);
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
#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
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/44279
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号