【学习笔记】同余最短路

【学习笔记】同余最短路

例题一：洛谷P3404 跳楼机

题目链接

题目大意：

有一幢 (h) 层的摩天大楼，你在第一层，你可以采用如下四种方式移动：

向上移动 (x) 层。
向上移动 (y) 层。
向上移动 (z) 层。
回到第一层。

问有多少楼层可以通过若干次移动到达。

数据范围：(1leq hleq 2^{63} - 1)，(1leq x,y,zleq 10^5)。

注意到一个重要性质：如果能到达楼层 (i)，那么楼层 (i + x, i + 2x, i + 3x,dots) 也都是可以到达的。形式化地说，所有 (j geq i) 且 (jequiv ipmod{x}) 的楼层 (j) 都是可以到达的。

所以我们考虑对所有 (kin[0, x))，求出可以到达的最小楼层 (i)，满足 (iequiv kpmod{x})。记这样的 (i) 为 (f(k))，那么答案就是：

[sum_{k = 0}^{x - 1}left(leftlfloorfrac{h - f(k)}{x} ight floor + 1 ight) ]

如何求出所有 (f(k))？用类似 DP 的方法，考虑 (k) 的转移。有如下两种：

(f(k) + y o f((k + y)mod x))
(f(k) + z o f((k + z)mod x))

其中 (a o b) 表示用 (a) 的值来更新 (b)。也就是 (b := min{a, b})。

这个转移不同于一般的 DP，它可能带有环。

我们可以用最短路算法来实现这个 DP。具体来说，从所有 (k)，分别向 ((k + y)mod x) 和 ((k + z)mod x) 连边，边权分别为 (y) 和 (z)。每一次转移，就和最短路中“松弛”的过程是一样的。起点是 (f(1mod x) = 1)。

最短路可以用 SPFA 算法实现，在本题的建图方式下，可以证明它不会被卡。时间复杂度 (mathcal{O}(x))。

参考代码：

// problem: P2371
#include <bits/stdc++.h>
using namespace std;

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 1e5, MAXM = MAXN * 2;
const ll LL_INF = 3e18;

ll h;
int x, y, z;

struct EDGE {
	int nxt, to, w;
} edge[MAXM + 5];
int head[MAXN + 5], tot;
void add_edge(int u, int v, int w) {
	edge[++tot].nxt = head[u];
	edge[tot].to = v;
	edge[tot].w = w;
	head[u] = tot;
}

ll dis[MAXN + 5];
bool inq[MAXN + 5];

int main() {
	cin >> h;
	cin >> x >> y >> z;
	
	for (int i = 0; i < x; ++i) {
		add_edge(i, (i + y) % x, y);
		add_edge(i, (i + z) % x, z);
	}
	
	for (int i = 0; i < x; ++i) {
		dis[i] = LL_INF;
	}
	dis[1 % x] = 1;
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		
		inq[u] = false;
		
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to;
			int w = edge[i].w;
			
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!inq[v]) {
					inq[v] = true;
					q.push(v);
				}
			}
		}
	}
	
	ll ans = 0;
	for (int i = 0; i < x; ++i) {
		if (dis[i] <= h) {
			ans += (h - dis[i]) / x + 1;
		}
	}
	cout << ans << endl;
	return 0;
}

例题二：洛谷P2371 [国家集训队]墨墨的等式

题目链接

题目大意：

给定 (n, a_{1dots n}, l, r)，请求出有多少整数 (bin[l,r]) 可以使关于 (x_{1dots n}) 的方程 (sum_{i = 1}^{n}a_i x_i = b) 存在非负整数解。

数据范围：(1leq nleq 12)，(0leq a_ileq 5 imes10^5)，(1leq lleq rleq 10^{12})。

首先特判所有 (a_i) 都等于 (0) 情况。

差分。求出 (leq r) 的 (b) 的数量，和 (leq l - 1) 的 (b) 的数量，相减得到答案。问题转化为对 (r)，求有多少 (bin[1, r])，使方程 (sum_{i = 1}^{n}a_i x_i = b) 有解。

与上一题类似，任选一个 (a_i eq 0)，记为 (p)。考虑在 (mod p) 意义下跑同余最短路。

具体来说，对于所有 (0leq i < p), (1leq jleq n)，从点 (i) 向点 ((i + a_j)mod p) 连一条边权为 (a_j) 的边。含义是，如果存在一个使方程有解的 (b)，满足 (bequiv ipmod{p})，那么 (b' = b + a_j) 也能使方程有解，且 (b'equiv i + a_jpmod{p})。

起点是 (0)，(f(0) = 0)。最终答案的计算方式与上题类似。

同样可以跑 SPFA。时间复杂度 (mathcal{O}(ncdot p) = mathcal{O}(ncdot min{a_i}))。

参考代码：

// problem: P2371
#include <bits/stdc++.h>
using namespace std;

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 5e5, MAXM = 5e5 * 12;
const ll LL_INF = 1e18;

int n, a[15], p;
ll L, R;

struct EDGE {
	int nxt, to, w;
} edge[MAXM + 5];
int head[MAXN + 5], tot;
void add_edge(int u, int v, int w) {
	edge[++tot].nxt = head[u];
	edge[tot].to = v;
	edge[tot].w = w;
	head[u] = tot;
}

ll dis[MAXN + 5];
bool inq[MAXN + 5];

int main() {
	cin >> n >> L >> R;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		if (a[i] == 0) {
			--i, --n;
		}
	}
	if (!n) {
		cout << 0 << endl;
		return 0;
	}
	sort(a + 1, a + n + 1);
	p = a[1];
	for (int i = 2; i <= n; ++i) {
		if (a[i] == a[i - 1])
			continue;
		for (int j = 0; j < p; ++j) {
			add_edge(j, (j + a[i]) % p, a[i]);
		}
	}
	
	for (int i = 0; i < p; ++i) {
		dis[i] = LL_INF;
	}
	dis[0] = 0;
	queue<int> q;
	q.push(0);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		
		inq[u] = false;
		
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to;
			int w = edge[i].w;
			
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!inq[v]) {
					inq[v] = true;
					q.push(v);
				}
			}
		}
	}
	
	ll ans = 0;
	--L;
	for (int i = 0; i < p; ++i) {
		if (dis[i] <= R) {
			ans += ((R - dis[i]) / p + 1);
		}
		if (dis[i] <= L) {
			ans -= ((L - dis[i]) / p + 1);
		}
	}
	cout << ans << endl;
	return 0;
}

小总结

同余最短路问题的关键，是找到一个数 (x)，满足：如果 (i) 合法，那么所有 (j geq i) 且 (jequiv ipmod{x}) 的 (j) 也合法。

这样，计数问题（求有多少合法的数），就转化为了最小值问题：对每个 (kin[0, x))，求出 (iequiv kpmod{x}) 的、最小的、合法的 (i)。

我们建图就直接在 ([0, x)) 这 (x) 个点上建就好了，转移也是描述的这 (x) 个点之间的关系。

例题三：【正睿联赛特训】巡回

题目大意：

给定一张 (n) 个点，(m) 条边的无向图。第 (i) 条边连接两个点 (u_i, v_i)，且有一个边权 (w_i)，无论从哪个方向经过这条边用时都是 (w_i)。你于 (0) 时刻从起点 (1) 出发，中途不在任何节点停留，可以经过重复的点和边（甚至起点和终点），你想要恰好在 (T) 时刻到达终点 (n)，问能否实现。

数据范围：(1leq n,mleq 50)，(1leq Tleq 10^{18})，(1leq w_ileq 10^4)。

考虑一条以 (n) 为端点的边 ((u, n, w))。注意到，如果能够在 (i) 时刻到达 (n)，那么通过在这条边上绕一下，也就可以在 (i + 2w) 时刻到达点 (n)。任取一条这样的边，记 (p = 2w)，考虑在 (mod p) 意义下跑同余最短路。

因为题目里本来就有一张图，所以我们考虑一个二维的 DP 状态：设 (f(u, k)) ((1leq uleq n), (0leq k < p)) 表示最小的时刻 (i)，满足 (iequiv kpmod{p})，且可以恰好在时刻 (i) 到达点 (u)。

转移是显然的。因为转移过程中可能存在环，所以我们同样用最短路算法来实现这个 DP。

答案就是 (f(n, Tmod p)) 是否 (leq T)。

时间复杂度 (mathcal{O}((n + m)cdot w))。

参考代码：

// problem: ZR1063
#include <bits/stdc++.h>
using namespace std;

#define mk make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;

template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }

const int MAXN = 50, MAXM = 50, MAXW = 1e4;
const int INF = 1e9;
const ll LL_INF = 3e18;

int n, m, p;
ll T;

ll dis[MAXN + 5][MAXW * 2];
bool inq[MAXN + 5][MAXW * 2];

struct EDGE {
	int nxt, to, w;
} edge[MAXM * 2 + 5];
int head[MAXN + 5], tot;
void add_edge(int u, int v, int w) {
	edge[++tot].nxt = head[u];
	edge[tot].to = v;
	edge[tot].w = w;
	head[u] = tot;
}

void solve_case() {
	cin >> n >> m >> T;
	tot = 0;
	for (int i = 1; i <= n; ++i) {
		head[i] = 0;
	}
	
	p = INF;
	for (int i = 1; i <= m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		++u, ++v;
		add_edge(u, v, w);
		add_edge(v, u, w);
		
		if (u == n || v == n) {
			ckmin(p, w * 2);
		}
	}
	
	if (p == INF) {
		cout << "Impossible" << endl;
		return;
	}
	
	queue<pii> q;
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < p; ++j) {
			dis[i][j] = LL_INF;
			inq[i][j] = false;
		}
	}
	dis[1][0] = 0;
	q.push(mk(1, 0));
	
	while (!q.empty()) {
		int u = q.front().fi;
		int t = q.front().se;
		q.pop();
		inq[u][t] = false;
		for (int i = head[u]; i; i = edge[i].nxt) {
			int v = edge[i].to;
			int w = edge[i].w;
			int tt = (w + t) % p;
			if (dis[v][tt] > dis[u][t] + w) {
				dis[v][tt] = dis[u][t] + w;
				if (!inq[v][tt]) {
					inq[v][tt] = true;
					q.push(mk(v, tt));
				}
			}
		}
	}
	
	if (dis[n][T % p] <= T) {
		cout << "Possible" << endl;
	} else {
		cout << "Impossible" << endl;
	}
	
}
int main() {
	int T; cin >> T; while (T--) {
		solve_case();
	}
	return 0;
}