同余最短路

P3403 假设 $x<y<z$ ,把 $H--$ ，让值域变成 $[0,H]$

1.设集合S, $$ S=\{l | l = by+cz\} $$ 也就是只用 $y$ 跟 $z$ 能到的楼层 则对每个 $l$ ,加上若干的 $x$ 也是答案。 但是 $S$ 中会有多个数与 $x$ 同余，导致重复统计答案。 参考1

2.思考选出 $S$ 中剩余类代表元进行答案的统计。 设 $S$ 中模 $x$ 为 $k$ 的剩余类中的最小值作为代表元 $f(k)$ 也就是说 $S$ 被 $mod x$ 的余数划分为多个集合，$f(k)$ 作为余数为 $k$ 的集合的最小值,该最小值作为代表元。

对这个群（显然）的代表元，有如下转移 $$ f(k) + y \ge f((k + y) \% x) $$ 先讨论y。则z同理 我们看一下+y的转移 如何证明 $f((k+y)\%x)$ 小于等于 $f(k) + y$ ？有 $$ f(k) \ge k $$

则 $$ f(k) + y \ge k + y $$

$$ f((k+y) \% x) \le f(k + y) \le k + y \le f(k) + y $$

不等式链成立.

那就可以用最短路进行求解了。

何意味呢？ 我又不知道 $f$ 咋求

其实现在是差分约束 也就是说，$0...x-1$ 这 $x$ 个结点 他们的 $f$ 就是他们的 $dis$

求出 $f$ 之后，对每个 $f$ 的元素统计答案

每个元素的答案是 $(H-f) / x + 1$

参考2

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

const ull maxn = 1e5 + 5;

const ull inf = ULLONG_MAX;

struct node {
	ull v, w;
};

vector<node> e[maxn];

void addedge(ull u, ull v, ull w)
{
	e[u].push_back({v, w});
}

vector<ull> dijkstra(ull n, ull s)
{
	vector<ull> dis(n, inf);
	vector<bool> vis(n, false);
	struct pqnode {
		ull u, dis;
		bool operator < (const pqnode &b) const {
			return dis > b.dis;
		}
	};
	priority_queue<pqnode> pq;

	dis[s] = 0;
	pq.push({s, dis[s]});

	while(!pq.empty()) {
		ull u = pq.top().u;
		pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(auto edge : e[u])
		{
			ull v = edge.v, w = edge.w;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				pq.push({v, dis[v]});
			}
		}
	}

	return dis;
}

int main()
{
	ull h, x, y, z;

	cin >> h >> x >> y >> z;

	h--;

	for(ull k = 0; k < x; k++)
	{
		addedge(k, (k + y) % x, y);
		addedge(k, (k + z) % x, z);
	}

	vector<ull> dis = dijkstra(x, 0);

	ull ans = 0;
	for(ull i = 0; i < x; i++)
	{
		// 注意S集合不一定有x的所有余数的代表元。
		if(dis[i] <= h)ans += (h - dis[i]) / x + 1;
	}
	cout << ans;
}