# [CSP-S 2026] 迁徙 / migrate 题解

思路

首先考虑暴力dp，考虑 \(f_i\) 为从点 \(i\) 到右边点最短路的方案，\(\operatorname{dist}(i,j)\) 为点 \(i\) 到点 \(j\) 的最短距离，那么有，枚举左端点 \(l\)：

\[\Large{f_i=\sum_{x_j + d \ge x_i且\operatorname{dist}(l,j) + 1 = \operatorname{dist}(l,i)}f_j} \]

时间复杂度 \(\Theta(n^3)\)

考虑如何优化。

\(\operatorname{dist}(l,i)\) 会把整个序列分成很多层，由于最短路一定是贪心的往更右边走，所以一层的转移只和上一层的最后三个有关，我们考虑当前一层的最后三个数的方案数分别为 \(x,y,z\) 。考虑记忆化搜索，但状态太多，记不下来

考虑转移过程。当 \(z = 2\) 时，只能从\(z\) 转移，否则当 \(z = 1,y = 1\) 就能从\(x, y\) 转移，否则无法转移。

于是可以把 \(z > 2,y>1,x>0\) 分别压成一种状态，就装的下了。

答案为 \(\sum_{i = 1}^n \operatorname{dfs}(i,0,0,1)\)

时间复杂度 \(\Theta(n)\)。

Code：

\(\text{C++Code:}\)

#include
#define int long long
using namespace std;
constexpr int MAXN = 2e6 + 5;
int f[MAXN][2][3][4];
int x[MAXN];
int nxt[MAXN];
int n, d;
int dfs(int cur, int x, int y, int z) {
	if (cur == n || !z || z > 2) return 0 ;
	if (~f[cur][x][y][z]) return f[cur][x][y][z];  
	int res = 0;
	int pos_x = x ? nxt[cur - 2] : cur,
		pos_y = y ? nxt[cur - 1] : cur,
		pos_z = z ? nxt[cur] : cur;
	int nxt_pos = nxt[cur];
	int nxt_x = 0, nxt_y = 0, nxt_z = 0;
	if (nxt_pos > cur) {
		nxt_z = z;
		if (pos_y >= nxt_pos) nxt_z += y;
		if (pos_x >= nxt_pos) nxt_z += x;
	}
	if (nxt_pos - 1 > cur) {
		nxt_y = z;
		if (pos_y >= nxt_pos - 1) nxt_y += y;
		if (pos_x >= nxt_pos - 1) nxt_y += x;
	}
	if (nxt_pos - 2 > cur) {
		nxt_x = z;
		if (pos_y >= nxt_pos - 2) nxt_x += y;
		if (pos_x >= nxt_pos - 2) nxt_x += x;
	} 
	if (z == 2) 
		res += pos_z - pos_y;
	else if (y == 1)
		res += pos_y - pos_x;
  
	res += dfs(nxt_pos, min(1ll, nxt_x), min(2ll, nxt_y), min(3ll, nxt_z));
	return f[cur][x][y][z] = res;
}
void solve() {
	cin >> n >> d;
	for (int i = 1; i <= n; ++i) 
		cin >> x[i];
	for (int l = 1, r = 1; l <= n; ++l) {
		while (r < n && x[l] + d >= x[r + 1]) ++r;
		nxt[l] = r;
	}
//	for (int i = 1; i <= n; ++i)
//		cerr << nxt[i] << ' ';
//	cerr << '\n';
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j < 2; ++j)
			for (int k = 0; k < 3; ++k)
				for (int l = 0; l < 4; ++l)
					f[i][j][k][l] = -1;
	for (int i = 1; i <= n; ++i)
		ans += dfs(i, 0, 0, 1);
	cout << ans << '\n';
}
signed main() {
#ifndef DEBUG
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	freopen("migrate.in", "r", stdin);
	freopen("migrate.out", "w", stdout);
#else
#endif
	int c, T;
	cin >> c >> T;
	while(T--) solve();
	return 0;
}