OI题解 - 机器人(LOJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - 机器人(LOJ)

发表于 分类于 Valine：

然而并没有AC……卡在85pt了

# 题面

> LOJ 3157

# 解析

首先可以得到一个 $O(n^2B)$ 的DP：定义 $f_{l,r,h}$ 表示区间 $[l,r]$ 中的所有数都 $\le h$ 的合法方案数。

那么可以得到一个非常朴素的转移方程：

其中 $m$ 满足 $m$ 与 $l,r$ 的距离相差不超过 2；且 $h\in[A_m,B_m]$

可以发现 $m$ 可以取的值最多只有 $3$ 个，所以转移是 $O(1)$ 的，因此时间复杂度就是状态复杂度 $O(n^2B)$。

根据 tly dalao 的说法，如果你胆大把 $n$ 开大一点，你可以通过一些 $n$ 比较大，按理论分析 $O(n^2B)$ 会TLE的点。为什么？我们发现，对于区间 $[L,R]$，我们都是找到区间中间的几个 $M$，把区间分成两段，类似于线段树（但是显然比线段树大），因此我们实际会用到的 $[l,r]$ 很少，不妨记这些区间的数量为 $m$。那么实际上复杂度是 $O(mB)$。

接下来就是拉格朗日插值的经典操作了：假设 $f_{l,r,h}$ 是关于 $h$ 的一个多项式函数 $F_{l,r}(h)$，设其次数为 $G(l,r)$。

根据转移式：$f_{l,r,h}-f_{l,r,h-1}=\sum\limits_{m}f_{l,m-1,h}\times f_{m+1,r,h-1}$，可以得到：

而 $l>r$ 时 $F_{l,r}(h)$ 是常数，即 $G(l,r)=0$。因此 $G(l,r)$ 大概是 $r-l+1$，即 $n$。

那么是不是我们只计算 $h\le n$ 的值就可以了呢？显然不是（不然它怎么会出现在NOI里）

我们发现与其他题不同的是有限制—— $h\in[A_i,B_i]$。如果取值范围不同，那么 $F_{l,r}(h)$ 就不是一个多项式函数——而是一个分段函数。

在每一段里 $F_{l,r}(h)$ 就是个多项式函数，于是对于每一段 $h\in[p,q]$，我们暴力计算前 $n$ 个值。根据转移式，我们知道在计算 $h\in[p,q]$ 的值时，最小只会用到 $f[l][r][p-1]$，因此我们计算出前 $n$ 个值后，再拉格朗日插值算出 $f[l][r][q]$，就可以接着转移了。

按 tly 的说法，这样应该是 95pt……估计我常数写大了，只有 85pt。

# 源代码

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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=310,M=3000,MOD=1e9+7;

inline int Add(const int &a,const int &b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(const int &a,const int &b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(const int &a,const int &b){return 1ll*a*b%MOD;}
inline int Pow(int a,int b){int r=1;while(b){if(b&1)r=Mul(r,a);a=Mul(a,a),b>>=1;}return r;}

int n,lef,rig,nbmap,nvis,beg;
int cap[N][2],bmap[N][N],cmap[M][2];
int dp[M][N],vis[M][N];
vector<int> uni;

int DP(int le,int ri,int hi){
	if(le>ri) return 1;
	if(!bmap[le][ri]) bmap[le][ri]=++nbmap,cmap[nbmap][0]=le,cmap[nbmap][1]=ri;
	int u=bmap[le][ri],h=hi-beg;
	if(h<0) return 0;
	if(vis[u][h]==nvis) return dp[u][h];
	dp[u][h]=0,vis[u][h]=nvis;
	int mid=(le+ri)>>1;
	dp[u][h]=DP(le,ri,hi-1);
	for(int i=mid-1;i<=mid+1;i++){
		int bet=(i-le)-(ri-i);
		if(bet<-2 || bet>2 || i<le || i>ri || hi<cap[i][0] || hi>cap[i][1]) continue;
		int nowh=min(hi,cap[i][1]);
		dp[u][h]=Add(dp[u][h],Mul(DP(le,i-1,nowh),DP(i+1,ri,nowh-1)));
	}
	return dp[u][h];
}
inline int Ri(){
	register int a=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') a=(a<<1)+(a<<3)+c-'0',c=getchar();
	return a;
}
int prep[N],sufp[N],fac[N],ifac[N];
int Poly(int u,int x){
	int ret=0;
	prep[0]=sufp[n+2]=1;
	for(int i=1;i<=n+1;i++) prep[i]=Mul(prep[i-1],Sub(x,i));
	for(int i=n+1;i>=1;i--) sufp[i]=Mul(sufp[i+1],Sub(x,i));
	for(int i=1;i<=n+1;i++){
		int tim1=Mul(dp[u][i],Mul(prep[i-1],sufp[i+1]));
		int tim2=Mul((n+1-i)&1? MOD-1:1,Mul(ifac[i-1],ifac[n+1-i]));
		ret=Add(ret,Mul(tim1,tim2));
	}
	return ret;
}
void Use(int le,int ri){
	if(le>ri) return;
	if(bmap[le][ri]) return;
	nbmap++;
	cmap[nbmap][0]=le,cmap[nbmap][1]=ri;
	bmap[le][ri]=nbmap;
	int mid=(le+ri)>>1;
	for(int i=mid-1;i<=mid+1;i++){
		int bet=(i-le)-(ri-i);
		if(bet<-2 || bet>2 || i<le || i>ri) continue;
		Use(le,i-1);Use(i+1,ri);
	}
}
int main(){
	freopen("robot.in","r",stdin);
	freopen("robot.out","w",stdout);
	fac[0]=1;
	for(int i=1;i<N;i++) fac[i]=Mul(fac[i-1],i);
	ifac[N-1]=Pow(fac[N-1],MOD-2);
	for(int i=N-2;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
	n=Ri();
	for(int i=1;i<=n;i++){
		cap[i][0]=Ri(),cap[i][1]=Ri();
		uni.push_back(cap[i][0]);
		uni.push_back(cap[i][1]+1);
	}
	uni.push_back(1);
	sort(uni.begin(),uni.end());
	uni.erase(unique(uni.begin(),uni.end()),uni.end());
	Use(1,n);
	for(int i=1;i<(int)uni.size();i++){
		lef=uni[i-1],rig=uni[i]-1;
		beg=lef-1;
		nvis++;
		for(int u=1;u<=nbmap;u++)
			for(int j=lef;j<=rig && j<=lef+n;j++)
				DP(cmap[u][0],cmap[u][1],j);
		for(int u=1;u<=nbmap;u++)
			if(rig<=lef+n) dp[u][0]=dp[u][rig-beg],vis[u][0]=nvis+1;
			else{
				if(!dp[u][n+1]) dp[u][0]=dp[u][n+1],vis[u][0]=nvis+1;
				else{
					dp[u][0]=Poly(u,rig-beg);
					vis[u][0]=nvis+1;
				}
			}
	}
	printf("%d\n",dp[bmap[1][n]][0]);
	return 0;
}

THE END

Thanks for reading!