【LOJ3157】「NOI2019」機器人

【題目連結】

• 點選打開連結

【思路要點】

• 考慮最右側的最大值所在的位置 i i i ，則 i i i 号位置的機器人一定會移動到邊界，并且擋住其他經過的機器人，是以枚舉 i i i 的位置可以将問題分解為左右兩個子問題分别處理。
• 注意到 i i i 可能的位置一定是靠近中點的，可能被通路到的區間數 M M M 不會是 O ( N 2 ) O(N^2) O(N2) 級别的，當 N ≤ 300 N\leq300 N≤300 時， M M M 大約在 2000 2000 2000 左右。
• 直接實作上述 d p dp dp ，可以得到一個時間複雜度 O ( M V ) O(MV) O(MV) 的做法。
• 考慮測試點 11 , 12 11,12 11,12 ，此時的轉移方式十分單一，并且可由歸納法證得長度為 x x x 的區間對應的 d p dp dp 值是一個不超過 x x x 次的多項式的點值。
• 是以若将權值分段，每一段的轉移與測試點 11 , 12 11,12 11,12 均無本質差別，是以每一段權值中，長度為 x x x 的區間對應的 d p dp dp 值同樣是一個不超過 x x x 次的多項式的點值。
• 配合拉格朗日插值，可以得到一個對于每一段權值，需要 O ( N M ) O(NM) O(NM) 的時間複雜度計算的算法，總時間複雜度為 O ( N 2 M ) O(N^2M) O(N2M) 。
• 由于維護多項式的做法複雜度為 O ( N 3 ) O(N^3) O(N3) ，略低于該做法，該做法隻能得到 95 95 95 分。但這做法不知道好寫到哪裡去了。
• 以下是筆者當場的 95 95 95 分做法的代碼。

【代碼】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 305;
const int MAXM = 3e3 + 5;
const int P = 1e9 + 7;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= f;
}
namespace Lagrange {
	const int P = 1e9 + 7;
	const int MAXN = 305;
	int fac[MAXN], inv[MAXN];
	void update(int &x, int y) {
		x += y;
		if (x >= P) x -= P;
	}
	int power(int x, int y) {
		if (y == 0) return 1;
		int tmp = power(x, y / 2);
		if (y % 2 == 0) return 1ll * tmp * tmp % P;
		else return 1ll * tmp * tmp % P * x % P;
	}
	void init(int n) {
		fac[0] = inv[0] = 1;
		for (int i = 1; i <= n; i++) {
			fac[i] = 1ll * fac[i - 1] * i % P;
			inv[i] = power(fac[i], P - 2);
		}
	}
	int getval(int n, int *x, int *y, int pos) {
		int ans = 0;
		static int pre[MAXN], suf[MAXN];
		for (int i = 0; i <= n; i++)
			if (i == 0) pre[i] = (pos - x[i] + P) % P;
			else pre[i] = 1ll * pre[i - 1] * (pos - x[i] + P) % P;
		for (int i = n; i >= 0; i--)
			if (i == n) suf[i] = (pos - x[i] + P) % P;
			else suf[i] = 1ll * suf[i + 1] * (pos - x[i] + P) % P;
		
		for (int i = 0; i <= n; i++) {
			int dom = 1, num = y[i];
			if (i != 0) {
				num = 1ll * num * pre[i - 1] % P;
				dom = 1ll * dom * inv[i] % P;
			}
			if (i != n) {
				num = 1ll * num * suf[i + 1] % P;
				dom = 1ll * dom * inv[n - i] % P;
			}
			if ((n - i) & 1) update(ans, P - 1ll * num * dom % P);
			else update(ans, 1ll * num * dom % P);
		}
		return ans;
	}
}
int n, m, Lim, Max, bench, home[MAXN][MAXN];
int a[MAXN], b[MAXN], dp[MAXM][MAXN], len[MAXM];
bool vis[MAXN][MAXN];
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int work(int l, int r) {
	if (l > r || vis[l][r]) return home[l][r];
	int mid = (l + r) / 2;
	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;
	}
	int cur = mid, u, v;
	if (mid - l == r - mid) {
		cur = mid - 1;
		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]) update(dp[now][i], 1ll * dp[u][i] * dp[v][i - 1] % P);
		}
		cur = mid;
		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]) update(dp[now][i], 1ll * dp[u][i] * dp[v][i - 1] % P);
		}
		cur = mid + 1;
		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]) update(dp[now][i], 1ll * dp[u][i] * dp[v][i - 1] % P);
		}
	} else {
		cur = mid;
		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]) update(dp[now][i], 1ll * dp[u][i] * dp[v][i - 1] % P);
		}
		cur = mid + 1;
		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]) update(dp[now][i], 1ll * dp[u][i] * dp[v][i - 1] % P);
		}
	}
	for (int i = 1; i <= Max; i++)
		update(dp[now][i], dp[now][i - 1]);
	vis[l][r] = true;
	return now;
}
int tot, e[MAXN * 2];
int main() {
	freopen("robot.in", "r", stdin);
	freopen("robot.out", "w", stdout);
	read(n), Max = 0;
	for (int i = 1; i <= n; i++) {
		read(a[i]), read(b[i]);
		chkmax(Max, b[i]);
		e[++tot] = a[i];
		e[++tot] = b[i] + 1;
	}
	sort(e + 1, e + tot + 1), Lim = n + 3;
	for (int i = 0; i <= Lim; i++)
		dp[0][i] = 1;
	Lagrange :: init(Lim);
	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, false, 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[MAXN];
				for (int j = 0; j <= Lim; j++)
					x[j] = bench + j;
				for (int j = 1; j <= m; j++)
					dp[j][0] = Lagrange :: getval(len[j] + 2, x, dp[j], e[i] - 1);
			}
			bench = e[i] - 1, Max = 1;
			memset(vis, false, sizeof(vis));
			work(1, n);
			for (int j = 1; j <= m; j++)
				dp[j][0] = dp[j][Max];
		}
	}
	cout << dp[home[1][n]][0] << endl;
	return 0;
}