洛谷 P5469 - [NOI2019] 机器人（区间 dp+拉格朗日插值）

洛谷题面传送门

神仙题，放在 D1T2 可能略难了一点（

首先显然对于 P 型机器人而言，将它放在 \(i\) 之后它会走到左边第一个严格 \(>a_i\) 的位置，对于 Q 型机器人而言，将它放在 \(i\) 之后它会走到右边第一个 \(\ge a_i\) 的位置，为了避免分类讨论我们可以假定 \(a_0=a_{n+1}=\infty\)。看到这个状态我们可以设计出一个区间 \(dp\)，\(dp_{l,r,x}\) 表示 \([l,r]\) 中的柱子最大值为 \(x\)，并且有 \(a_{l-1}>x,a_{r+1}\ge x\) 的方案数，再设 \(sum_{l,r,x}\) 表示 \(dp_{l,r,x}\) 的前缀和，那么我们显然可以枚举最靠后的最大值的位置 \(t\)，那么对于放在 \(t\) 的 P 型机器人，显然它会走到 \(l-1\)，Q 型机器人会走到 \(r+1\)，因此 \(dp_{l,r,x}\) 可以从 \(t\) 转移的充要条件是 \(|(t-l)-(r-t)|\le 2\) 且 \(x\in[a_l,a_r]\)，因此转移是常数级别的，这样暴力做是 \(\mathcal O(n^2A)\) 的，其中 \(A=\max\{b_i\}\)，可以拿到 \(35\) 分的好成绩，不过注意到对于一个区间而言，它只可能从靠中间的位置转移过来，也就是说很多 DP 状态是转移不到 \(dp_{1,n,*}\) 的，打个表可以发现有用的区间最多 \(2518\) 个，因此写个记搜，再卡卡常即可拿到 \(50\) 分。

接下来思考正解，注意到有一档部分分是 \(A_i=1,B_i=10^9\)，咱们不妨来当回心理学家（大雾），思索一下，这档部分分有啥用？\(A_i=1,B_i=10^9\) 意味着所有 \(10^9\) 以内的正整数都可以成为柱子的高度，也就是说 \(x\in[a_l,a_r]\) 这个条件就没有用了，因此我们只用关心 \(|(t-l)-(r-t)|\le 2\) 这个条件即可。接下来再思索一下，\(B_i\) 这么大，出题人会让我们干嘛？显然对于 \(l=r\) 时，\(dp_{l,r,x}=1,sum_{l,r,x}=x\)，而对于 \(r-l=1\) 的情况，\(dp_{l,r,x}\) 会从 \(sum_{l,l,x}\) 或 \(sum_{r,r,x}\) 转移过来，因此 \(dp_{l,r,x}\) 可以写成 \(kx\) 的形式，\(sum_{l,r,x}\) 也就可以写成 \(Ax^2+Bx\) 的形式……对！多项式！通过上面的观察可以发现，\(dp_{l,r,x}\) 是关于 \(x\) 的 \(r-l\) 次多项式，\(sum_{l,r,x}\) 是关于 \(x\) 的 \(r-l+1\) 次多项式，证明可以归纳。我们可以求出 \(sum_{l,r,x}\) 的任意 \(r-l\) 个点值，然后把这个多项式插出来即可通过 \(11,12\) 这两个测试点，由于点值连续，插值可以线性。

考虑满分做法，既然有了 \(A_i,B_i\) 的限制，并且它们范围这么大，那肯定要离散化咯，我们按照这题的套路将每个区间看作一个左开右闭的区间 \([A_i,B'_i)\)，其中显然 \(B'_i=B_i+1\)，然后离散化。这样一来一个数 \(i\) 就可以代表一个左开右闭的区间 \([C_i,C_{i+1})\)。按照之前的思路我们猜想在每个这样左开右闭的区间中，\(dp_{l,r,x}\) 是关于 \(x\) 的 \(r-l\) 次多项式，\(sum_{l,r,x}\) 是关于 \(x\) 的 \(r-l+1\) 次多项式，事实上这个猜想也是正确的，读者自证不难。因此考虑从小到大枚举每个区间，然后对每个 \(l,r\)，求出该区间中最小的 \(\min(C_{i+1}-C_i,n+1)\) 个数的点值即可，具体实现就每次枚举一个 \(C_i\) 就开个数组 sum[l][r][x] 表示上文中所说的 \(sum_{l,r,C_i+x-1}\)，dp[l][r][x] 表示上文中所说的 \(dp_{l,r,C_i+x-1}\)，按照上面的套路转移 dp[l][r][x] 即可，求完所有区间的 dp 后对每个区间进行一遍插值，求出 \(sum_{l,r,x}\)，在 \(C_{i+1}-1\) 处的点值，然后把它存入新的 sum[l][r][0] 即可，正确性显然，复杂度 \(\mathcal O(2518n^2)\)，轻微卡常（不过对于我这个卡常菜鸡来说就得交 \(114514191981019260817998244353\) 发咯），得用一些卡常技巧，这里稍微介绍一下我的卡常技巧：

对区间 \([l,r]\) 进行插值的时候，可以只用前 \(r-l+1\) 个点值插值，不用插 \(n+1\) 个点值。
可以特判掉 \(C_{i+1}-C_i\le n\) 的情况，这样 \(C_{i+1}-1\) 处的点值我们在 DP 的时候已经求出来了
插值不必按部就班地求出前缀后缀积，由于我们已经特判掉了 \(C_{i+1}-C_i\le n\) 的情况，因此一定有 \(C_i+j-1\ne C_{i+1},j\in[1,n+1]\)，此时只要预处理一遍每个 \(C_{i}+j-1\) 的逆元然后那全部 \(C_i+j-1\) 的乘积乘上对应的逆元即可。

const int MAXN=300;

const int MOD=1e9+7;

const int MAXS=2520;

void add(int &x,int y){((x+=y)>=MOD)&&(x-=MOD);}

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int n,a[MAXN+5],b[MAXN+5],key[MAXN*2+5],uni[MAXN*2+5],num=0;

int id[MAXN+5][MAXN+5],itvl_n=0;pii itvls[MAXS+5];

void find_itvl(int l,int r){

	if(id[l][r]) return;id[l][r]=++itvl_n;

	itvls[itvl_n]=mp(l,r);if(l>r) return;

	for(int i=l;i<=r;i++) if(abs((i-l)-(r-i))<=2)

		find_itvl(l,i-1),find_itvl(i+1,r);

}

int dp[MAXS+5][MAXN+5];bool vis[MAXN+5][MAXN+5];

void work(int l,int r,int len,int itv){

	if(l>r){

		for(int i=0;i<=len;i++) dp[id[l][r]][i]=1;

		return;

	} if(vis[l][r]) return;vis[l][r]=1;

	for(int i=1;i<=len;i++) dp[id[l][r]][i]=0;

	for(int x=l;x<=r;x++) if(abs((x-l)-(r-x))<=2) if(a[x]<=itv&&itv<b[x]){

		work(l,x-1,len,itv);work(x+1,r,len,itv);

		for(int i=1;i<=len;i++){

			dp[id[l][r]][i]=(dp[id[l][r]][i]+1ll*

			dp[id[l][x-1]][i]*dp[id[x+1][r]][i-1])%MOD;

		}

	}

	for(int k=1;k<=len;k++) add(dp[id[l][r]][k],dp[id[l][r]][k-1]);

}

int iv[MAXN+5],ifac[MAXN+5];

void init_fac(int n){

	for(int i=(ifac[0]=ifac[1]=1)+1;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;

	for(int i=1;i<=n;i++) ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;

}

void getval(int l,int r){

	if(r-l+1<=n+1){

		for(int i=1;i<=itvl_n;i++) dp[i][0]=dp[i][r-l+1];

		return;

	} for(int i=1;i<=n+1;i++) iv[i]=qpow(r-(l+i-1),MOD-2);

	for(int i=1;i<=itvl_n;i++){

		if(itvls[i].fi>itvls[i].se) continue;

		int len=itvls[i].se-itvls[i].fi+1,tot=1;

		for(int j=1;j<=len+1;j++) tot=1ll*tot*(r-(l+j-1))%MOD;

		dp[i][0]=0;

		for(int j=1;j<=len+1;j++){

			int mul=1ll*ifac[j-1]*ifac[len+1-j]%MOD*tot%MOD*iv[j]%MOD;

			if((len+1-j)&1) mul=MOD-mul;

			dp[i][0]=(dp[i][0]+1ll*mul*dp[i][j])%MOD;

		}

	}

}

int main(){

//	freopen("robot.in","r",stdin);

//	freopen("robot.out","w",stdout);

	scanf("%d",&n);init_fac(n+3);

	for(int i=1;i<=n;i++){

		scanf("%d%d",&a[i],&b[i]);++b[i];

		key[i*2-1]=a[i];key[i*2]=b[i];

	} sort(key+1,key+(n<<1)+1);

	for(int i=1;i<=n<<1;i++) if(key[i]^key[i-1])

		uni[++num]=key[i];

	for(int i=1;i<=n;i++){

		a[i]=lower_bound(uni+1,uni+num+1,a[i])-uni;

		b[i]=lower_bound(uni+1,uni+num+1,b[i])-uni;

	} find_itvl(1,n);

	for(int i=1;i<num;i++){

//		printf("%d %d\n",uni[i],uni[i+1]-1);

		memset(vis,0,sizeof(vis));

		for(int l=1;l<=n;l++) for(int r=l-1;r<=n;r++)

			if(id[l][r]) work(l,r,min(uni[i+1]-uni[i],n+1),i);

		getval(uni[i],uni[i+1]-1);

//		for(int j=1;j<=itvl_n;j++) printf("%d %d %d\n",i,j,dp[j][0]);

	} printf("%d\n",dp[id[1][n]][0]);

	return 0;

}

洛谷 P5469 - [NOI2019] 机器人（区间 dp+拉格朗日插值）的相关教程结束。