知识点：DP，最短路
Link：Luogu
最短路算法本质上还是一种 DP。这里是借用了最短路来优化 DP。
简述
给定参数 \(h, x, y, z\)，求 \([1, h]\) 中有多少数 \(i\) 能被表示成 \(i = (k_1\times x + k_2\times y + k_3\times z + 1)\ (k_1, k_2, k_3\in \N)\) 的形式。
\(1\le h\le 2^{63} - 1\)，\(1\le x, y, z\le 10^5\)。
1S，128MB。
分析
只能说这种做法太妙了……实在是不知道怎么梳理出一个合理的思路，直接写做法了。
首先令 \(h-1\)，求 \([0, h-1]\) 中有多少数 \(i\) 能被表示成 \(i = k_1\times x + k_2\times y + k_3\times z\ (k_1, k_2, k_3\in \N)\) 的形式。
我们在 \(\bmod x\) 意义下考虑使用 \(y, z\) 能组合出的数，记 \(f_{i}\) 为满足 \(f_{i} \bmod x = i\) 的最小的数。显然对于大于 \(f_i\) 且满足 \(j\bmod x = i\) 的所有数 \(j\)，都可以通过在 \(f_{i}\) 基础上加数个 \(x\) 凑出来，而小于 \(f_i\) 且满足 \(j\bmod x = i\) 的所有数 \(j\) 均是无法被凑出来的，这些合法的数的数量为：\(\left\lfloor \frac{h- f_i}{x} \right\rfloor + 1\)。
问题变为如何快速处理出 \(f_i\)。考虑 DP。初始化 \(f_{0} = 0\)，则可以写出一个粗陋的式子：
\[f_i = \min_{(j + y) \equiv i \lor (k + z) \equiv i \pmod x}\{ f_{j} + y, f_k + z\} \]发现由于枚举顺序难以确定，这个转移是没法直接做的。但它的形式和性质和求最短路是一致的，于是考虑建图转化成求最短路。建立一张 \(x\) 个节点的有向带权图，从节点 0 到节点 \(i(0\le i\le n - 1)\) 的最短路即为 \(f_i\)。建图时枚举 \(u\in [0, n - 1]\)，从 \(u\) 向 \((u + y)\bmod x\) 连一条权值为 \(y\) 的有向边，向 \((u + z)\bmod x\) 连一条权值为 \(z\) 的有向边。跑出来最短路即可计算答案。
总时间复杂度 \(O(x\log x)\) 级别。
代码
//By:Luckyblock
/*
*/
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 1e5 + 10;
const int kM = kN << 1;
//=============================================================
int x, y, z;
LL h, ans, dis[kN];
int edgenum, head[kN], v[kM], w[kM], ne[kM];
bool vis[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = - 1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + ch - '0';
return f * w;
}
void Add(int u_, int v_, int w_) {
v[++ edgenum] = v_;
w[edgenum] = w_;
ne[edgenum] = head[u_];
head[u_] = edgenum;
}
void Dijkstra() {
memset(dis, 63, sizeof (dis));
std::priority_queue <pr <LL, int> > q;
dis[0] = 0;
q.push(mp(0, 0));
while (!q.empty()) {
int u_ = q.top().second; q.pop();
if (vis[u_]) continue;
vis[u_] = true;
for (int i = head[u_]; i; i = ne[i]) {
int v_ = v[i], w_ = w[i];
if (dis[u_] + 1ll * w_ < dis[v_]) {
dis[v_] = dis[u_] + w_;
q.push(mp(-dis[v_], v_));
}
}
}
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
scanf("%lld\n", &h); -- h;
x = read(), y = read(), z = read();
for (int i = 0; i < x; ++ i) {
Add(i, (i + y) % x, y);
Add(i, (i + z) % x, z);
}
Dijkstra();
for (int i = 0; i < x; ++ i) {
if (h >= dis[i]) ans += 1ll * (h - dis[i]) / x + 1;
}
printf("%lld\n", ans);
return 0;
}