P3403 跳楼机

新科技 同余最短路 题目链接

先考虑后两种走法能走到的楼层.
按照模数分类, 具体\(f[i]\)表示最小的楼层使\(f[i]\bmod x=i\),

为什么要这样做呢？
因为能到达的楼层无非就是\(ax+by+cz\)
我们当\(x\text{,}y\)固定时，方案数是\(\left\lfloor\frac{h-x-y}{z}\right\rfloor\)
我们考虑所有\(ax+by\)，都可以算出对应的方案。
但是发现这样会算重复一些楼层。
可以发现当\(ax+by\equiv a'x+b'y \pmod z\)会重复计算
显然这时候我们只需要保留最小的\(ax+by\)就可以了
所以按照\(\bmod z\)的每一个余数分类，保留最小的楼层即可。

最后答案\(\sum\limits_{i=0}^{x-1}\left\lfloor\frac{h-f[i]}{x}\right\rfloor +1\text{,}f[i]\leq h\).
加 1 是因为要算上只用后两个方法走到的楼层.
这样统计是不重不漏的.

那么怎么算\(f\)呢？ 根据同余方程的性质, 可以有转移
\(f[(i+y)\bmod x]=f[i]+y\)
\(f[(i+z)\bmod x]=f[i]+z\)

因为\(f[i]=ay+bz\)
即\(ay+bz\equiv i\pmod x\)
以第一个转移为例，\(f[i]+y=ay+bz+y\)
\(ay+bz+y\)在模\(x\)的意义下和\(i+y\)同余。
但是这样转移并不一定\(f[i]+y\)就是最小的楼层。

这个方程可以用最短路来求解, 具体建图方法

for (int i = 0; i < x; i++) add(i, (i + y) % x, 1ll *  y), add(i, (i + z) % x, 1ll *  z);
```  

注意图的部分数组要开两倍.  

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
int x, y, z, head[N], cnt;
ll dis[N];

struct E {
	int nxt, v; ll w;
} e[N];

void add(int u, int v, ll w) {e[++cnt] = (E){head[u], v, w}; head[u] = cnt;}
void SPFA(int s) {
	queue<int> q;
	bool vis[N] = {};
	memset(dis, 0x3f, sizeof dis);
	dis[s] = 1; q.push(s), vis[s] = 1;
	while (!q.empty()) {
		int now = q.front(); q.pop(), vis[now] = 0;
		for (int i = head[now]; i; i = e[i].nxt) {
			int v = e[i].v; ll w = e[i].w;
			if (dis[now] + w < dis[v]) {
				dis[v] = dis[now] + w;
				if (!vis[v]) q.push(v), vis[v] = 1;
			}
		}
	}
}

int main() {
	ll h = 0, ans = 0;
    scanf("%lld %d %d %d", &h ,&x, &y, &z);
    if (x == 1 || y == 1 || z == 1) {printf("%lld\n", h); return 0;}
    for (int i = 0; i < x; i++) add(i, (i + y) % x, 1ll *  y), add(i, (i + z) % x, 1ll *  z);
    SPFA(1);
    for (int i = 0; i < x; i++) if ((ll)dis[i] <= h) ans = ans + (h - (ll)(dis[i])) / (ll)(x) + 1ll;
    printf("%lld\n", ans);
    return 0;
}