[NOI2019] 机器人[DP] [拉格朗日插值]

传送门

N O I 2019 NOI 2019 NOI2019 的第5道，听说可以用下降幂维护，但是我用拉格朗日插值怼过去了

考虑暴力的 d p dp dp， f l , r , k f_{l,r,k} fl,r,k​表示区间 [ l , r ] [l,r] [l,r] 的最大值为 k k k 的方案数

枚举最高点位置，显然并没有东西可以挡住最高点，因此

如果区间为奇数， p ∈ [ m i d − 1 , m i d + 1 ] p\in [mid-1,mid+1] p∈[mid−1,mid+1]

如果区间为偶数， p ∈ [ m i d , m i d + 1 ] p\in [mid,mid+1] p∈[mid,mid+1]

f l , r , k = ∑ x ≤ k f l , p − 1 , x + ∑ x < k f p + 1 , r , x f_{l,r,k}=\sum_{x\le k}f_{l,p-1,x}+\sum_{x<k} f_{p+1,r,x} fl,r,k​=∑x≤k​fl,p−1,x​+∑x<k​fp+1,r,x​

然后发现 p p p 每次取的值很少，于是总的区间个数 M M M应该不会很多

于是就有 O ( M V ) O(MV) O(MV) 的算法

考虑 A i = 1 , B i = 1 e 9 A_i=1,B_i=1e9 Ai​=1,Bi​=1e9 ，转移十分的单一，猜想它是一个关于 k k k 的多项式

首先对于 l = r l=r l=r， f f f 是一个常数，然后每次将 f f f 前缀和后加起来就会多一次，两边乘起来次数相当与加起来， f f f 是一个不超过 r − l + 1 r-l+1 r−l+1 次的多项式

考虑先按权值排序，分段， [ v i − 1 , v i − 1 ] [v_{i-1},v_i-1] [vi−1​,vi​−1] 的转移类似 A i = 1 , B i = 1 e 9 A_i=1,B_i=1e9 Ai​=1,Bi​=1e9

我们只需要暴力维护 n n n 项 d p dp dp 的值，然后可以通过拉格朗日插出 v i − 1 v_i-1 vi​−1 的 d p dp dp 值

复杂度 O ( n 2 m ) O(n^2m) O(n2m)， l u o g u luogu luogu 开 O 2 O_2 O2​可以A

#include<bits/stdc++.h>
#define N 305
#define M 3005
using namespace std;
int read(){
	int cnt = 0, f = 1; char ch = 0;
	while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;}
	while(isdigit(ch)) cnt = (cnt << 1) + (cnt << 3) + (ch-'0'), ch = getchar();
	return cnt * f;
}
#define cs const
cs int Mod = 1e9 + 7;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b;}
int mul(int a, int b){ return 1ll * a * b % Mod;}
int power(int a, int b){int ans=1; for(;b;b>>=1,a=mul(a,a)) if(b&1) ans=mul(ans,a); return ans;}
void Add(int &a, int b){ a = add(a, b);}

int home[N][N], dp[M][N], len[M];
bool vis[N][N];
int n, m, bench, a[N], b[N];
int e[N << 1], tot, Max;
int lim, x[N]; // lagrange 
int fac[N], inv[N];
void prework(){
	fac[0] = fac[1] = inv[0] = inv[1] = 1;
	for(int i = 2; i <= lim; i++) fac[i] = mul(fac[i-1], i);
	inv[lim] = power(fac[lim], Mod-2);
	for(int i = lim-1; i >= 2; i--) inv[i] = mul(inv[i+1], i+1); 
}
void get(int now, int l, int r, int cur);
int work(int l, int r){
	if(l > r || vis[l][r]) return home[l][r];
	int mid = (l+r) >> 1;
	if(home[l][r] == 0){
		home[l][r] = ++m;
		len[m] = r-l+1;
	} int now = home[l][r];	
	for(int i = 1; i <= Max; i++) dp[now][i] = 0;
	if(l == r){
		for(int i = 1; i <= Max; i++)
			dp[now][i] = dp[now][i-1] + (i + bench >= a[l] && i + bench <= b[l]);
		return now;
	}
	if(mid - l == r - mid){ get(now, l, r, mid - 1); get(now, l, r, mid); get(now, l, r, mid + 1); }
	else{ get(now, l, r, mid); get(now, l, r, mid + 1);}
	for(int i = 1; i <= Max; i++) Add(dp[now][i], dp[now][i-1]);	
	vis[l][r] = 1;
	return now;
}
void get(int now, int l, int r, int cur){ 
	int u = work(l, cur - 1), v = work(cur + 1, r);
	for(int i = 1; i <= Max; i++)
		if(i + bench >= a[cur] && i + bench <= b[cur])
			Add(dp[now][i], mul(dp[u][i], dp[v][i-1]));
}
int lagrange(int n, int *x, int *y, int pos){
	static int pre[N], suf[N];
	pre[0] = add(pos, Mod - x[0]);
	suf[n] = add(pos, Mod - x[n]);
	for(int i = 1; i <= n; i++) pre[i] = mul(pre[i-1], add(pos, Mod - x[i]));
	for(int i = n-1; i >= 0; i--) suf[i] = mul(suf[i+1], add(pos, Mod - x[i]));
	int ans = 0;
	for(int i = 0; i <= n; i++){
		int tmp = 1;
		if(i) tmp = mul(tmp, mul(inv[i], pre[i-1]));
		if(i^n) tmp = mul(tmp, mul(inv[n-i], suf[i+1]));
		if((n-i) & 1) tmp = Mod - tmp; ans = add(ans, mul(y[i], tmp));
	} return ans;
}
int main(){
	n = read(); lim = n + 3; prework();
	for(int i = 1; i <= n; i++){
		a[i] = read(), b[i] = read();
		Max = max(Max, b[i]);
		e[++tot] = a[i], e[++tot] = b[i] + 1;
	} sort(e + 1, e + tot + 1);
	for(int i = 0; i <= lim; i++) dp[0][i] = 1;
	for(int i = 1; i <= tot; i++){
		if(e[i] != e[i-1]){
			bench = e[i-1];
			Max = min(lim, e[i] - e[i-1] - 1);
			memset(vis, 0, sizeof(vis));
			work(1, n);
			if(Max == e[i] - e[i-1] - 1){
				for(int j = 1; j <= m; j++)
					dp[j][0] = dp[j][Max];
			} else{
				static int x[N];
				for(int j = 0; j <= lim; j++)
					x[j] = bench + j;
				for(int	j = 1; j <= m; j++){
					dp[j][0] = lagrange(len[j] + 2, x, dp[j], e[i] - 1);
				}
			} bench = e[i] - 1; Max = 1;
			memset(vis, 0, sizeof(vis));
			work(1, n);
			for(int j = 1; j <= m; j++)
				dp[j][0] = dp[j][Max];
		}
	} cout << dp[home[1][n]][0]; return 0;
}