同余最短路

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;
}