同余最短路可以用于解决形如 “给定 \(n\) 个整数，求这 \(n\) 个整数能拼凑出多少的其他的整数（\(n\) 个整数可以重复选取）”以及“给定 \(n\) 个整数，求这 \(n\) 个整数不能拼凑出的最小（最大）的整数”，或者“至少要拼几次才能拼出模 \(k\) 余 \(p\) 的数”的问题的时候可以使用同余最短路的方法。

【资料图】

同余最短路利用同余来构造一些状态，可以达到优化空间复杂度的目的。

类比差分约束的方法，利用同余构造的这些状态可以看作单源最短路中的点，同余最短路的状态转移通常是这样的：\(f(i + y) = f(i) + y\)，类似单源最短路中的 \(f(v) = f(u) + edge(u,v)\)。

我们在做题的过程中就是需要找到最小的剩余系，然后根据其余数建图，然后跑最短路，利用求得的 \(dis\) 来解题。

我们发现有三种操作，分别是加 \(x,y,z\)，那么我们就可以把里面最小的当作取余的模数，然后开始建图，这里我们不难发现，只有当 \(n\ge dis_{i}\) 的时候，我们当前楼层是可以到的，因为是余数，所以加上的是 \(\frac{n-dis_{i}}{x} + 1\)。

#include #define pii pair#define INF 0x3f3f3f3f#define int long long#define N 1001000using namespace std;int n, x, y, z, dis[N], vis[N], head[N], cnt, ans;struct sb{int u, v, w, next;}e[N];priority_queue, greater > q;inline void add(int u, int v, int w) {e[++ cnt] = {u, v, w, head[u]}; head[u] = cnt;}inline void Dij(){memset(dis, INF, sizeof dis);dis[1] = 1; q.push({1, 1});while(!q.empty()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = 1;for(int i = head[u]; i; i = e[i].next){int v = e[i].v;if(dis[v] > dis[u] + e[i].w)dis[v] = dis[u] + e[i].w, q.push({dis[v], v});}}return ;}signed main(){cin >> n >> x >> y >> z;if(x == 1 || y == 1 || z == 1) return cout << n << endl, 0;for(int i = 0; i < x; i ++){add(i, (i + y) % x, y);add(i, (i + z) % x, z);}Dij();for(int i = 0; i < x; i ++)if(n >= dis[i]) ans += (n - dis[i]) / x + 1;cout << ans << endl;return 0;}

我们看到实际上能用的板子是 \(m\times n\) 个的。

我们考虑找出来最小的板子，如果长度小于等于 \(1\)，那么所有的围栏长度都能拼出来。

否则我们就正常对其进行建图，这里要注意尽量避免重边，然后跑 dij 就好了。

最后如果要是 \(dis_{i}\) 到达不了，说明就是拼不出来，没有最大值。

#include #define pii pair#define int long long#define INF INT_MAX#define N 2000100using namespace std;int n, m, a[N], xx, head[N], cnt, vis[N], dis[N], ans;struct sb{int u, v, w, next;}e[N];priority_queue, greater > q;inline void add(int u, int v, int w) {e[++ cnt] = {u, v, w, head[u]}; head[u] = cnt;}inline void Dij(){for(int i = 0; i <= xx; i ++) dis[i] = INF;dis[0] = 0; q.push({0, 0});while(!q.empty()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = 1;for(int i = head[u]; i; i = e[i].next){int v = e[i].v;if(dis[v] > dis[u] + e[i].w)dis[v] = dis[u] + e[i].w, q.push({dis[v], v});}}return ;}signed main(){cin >> n >> m;for(int i = 1; i <= n; i ++)cin >> a[i];sort(a + 1, a + n + 1);xx = max(1ll, a[1] - m);//找最小的剩余系 if(xx == 1) return cout << "-1" << endl, 0;for(int i = 1; i <= n; i ++)for(int j = max(a[i - 1] + 1, a[i] - m); j <= a[i]; j ++) // 枚举可以建边的情况 if(j != xx)//如果不相等 for(int k = 0; k < xx; k ++)//枚举所有余数建边 add(k, (k + j) % xx, j);Dij();dis[xx] = 0;for(int i = 1; i < xx; i ++){if(dis[i] == INF) return cout << "-1" << endl, 0;//不存在最大值 ans = max(ans, dis[i] - xx);//找最大不能拼出来的长度 }cout << ans << endl;return 0;}

和上面的区别就是多了几个按键。

我们同样还是找最小的剩余系，然后我们就直接开始建图跑最短路。

需要注意：边很多，数组开大；INF 一定要大，最好是 LONG_LONG_MAX。

我们询问的是区间 \([l,r]\)，所以我们可以用前缀和思想，用 \([1,r]\) 的答案减去 \([1, l- 1]\) 的答案即可。

统计答案的时候就是计算符合 \(dis[i]\le x\) 的 \(\frac{x-dis_{i}}{minn} + 1\) 即可，和上面几乎一样的。

#include #define pii pair#define INF LONG_LONG_MAX#define int long long#define N 10001000#define M 100100using namespace std;int n, m, a[N], l, r, minn = INF, dis[N], vis[N], cnt, head[N];struct sb{int u, v, w, next;}e[N];priority_queue, greater > q;inline void add(int u, int v, int w){e[++ cnt] = {u, v, w, head[u]}; head[u] = cnt;}inline void Dij(){for(int i = 0; i <= minn; i ++) dis[i] = INF;dis[0] = 0; q.push({0, 0});while(!q.empty()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = 1;for(int i = head[u]; i; i = e[i].next){int v = e[i].v;if(dis[v] > dis[u] + e[i].w)dis[v] = dis[u] + e[i].w, q.push({dis[v], v});}}return ;}inline int ask(int x){int res = 0;for(int i = 0; i < minn; i ++)if(dis[i] <= x) res += (x - dis[i]) / minn + 1;return res;}signed main(){cin >> n >> l >> r;for(int i = 1; i <= n; i ++){int x; cin >> x;if(x)a[++ m] = x, minn = min(x, minn);}n = m;for(int i = 0; i < minn; i ++)for(int j = 1; j <= m; j ++)if(a[j] != minn) add(i, (i + a[j]) % minn, a[j]);Dij();cout << ask(r) - ask(l - 1) << endl;return 0;}