AIOJ

当出现形如「给定 $n$ 个整数，求这 $n$ 个整数能拼凑出多少的其他整数（ $n$ 个整数可以重复取）」，以及「给定 $n$ 个整数，求这 $n$ 个整数不能拼凑出的最小（最大）的整数」，或者「至少要拼几次才能拼出模 $K$ 余 $p$ 的数」的问题时可以使用同余最短路的方法．

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

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

例题

例题一

P3403 跳楼机

题目大意：给定 $x，y，z，h$ ，对于 $k \in [1,h]$ ，有多少个 $k$ 能够满足 $ax+by+cz=k$ ．（ $0\leq a,b,c$ ， $1\le x,y,z\le 10^5$ ， $h\le 2^{63}-1$ ）

不妨假设 $x < y < z$ ．

令 $d_i$ 为只通过 操作 2 和 操作 3，需满足 $p\bmod x = i$ 能够达到的最低楼层 $p$ ，即 操作 2 和 操作 3 操作后能得到的模 $x$ 下与 $i$ 同余的最小数，用来计算该同余类满足条件的数个数．

可以得到两个状态：

$i \xrightarrow{y} (i+y) \bmod x$
$i \xrightarrow{z} (i+z) \bmod x$

注意通常选取一组 $a_i$ 中最小的那个数对它取模，也就是此处的 $x$ ，这样可以尽量减小空间复杂度（剩余系最小）．

那么实际上相当于执行了最短路中的建边操作：

add(i, (i+y) % x, y)

add(i, (i+z) % x, z)

接下来只需要求出 $d_0, d_1, d_2, \dots, d_{x-1}$ ，只需要跑一次最短路就可求出相应的 $d_i$ ．

基于最短路的实现

#include <iostream>
#include <queue>

using namespace std;
using ll = long long;
constexpr int MAXN = 100010;
constexpr ll linf = (1ull << 63) - 1;

ll h, x, y, z;
ll head[MAXN << 1], tot;
ll dis[MAXN], vis[MAXN];
queue<int> q;

struct edge {
  ll to, next, w;
} e[MAXN << 1];

void add(ll u, ll v, ll w) {
  e[++tot] = edge{v, head[u], w};
  head[u] = tot;
}

void spfa() {  // spfa算法，可看最短路部分
  dis[0] = 0;
  vis[0] = 1;
  q.push(0);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].to, w = e[i].w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        if (!vis[v]) {
          q.push(v);
          vis[v] = 1;
        }
      }
    }
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> h;
  cin >> x >> y >> z;
  if (x == 1 || y == 1 || z == 1) {
    cout << h << '\n';
    return 0;
  }
  --h;
  for (int i = 0; i < x; i++) {
    add(i, (i + z) % x, z);
    add(i, (i + y) % x, y);
    dis[i] = linf;
  }
  spfa();
  ll ans = 0;
  for (int i = 0; i < x; i++) {
    if (h >= dis[i]) ans += (h - dis[i]) / x + 1;
  }
  cout << ans << '\n';
  return 0;
}

但是事实上也不需要进行正常的最短路求解，注意到有两个特殊的性质：

首先，只有两种边权，且对于每一条路径，由于加法交换律，走两种边权的顺序是无影响的．因此可以考虑做两次最短路，每次只建出一类边权的边；

其次，对于只有一类边权的图，每个点 $u$ 都有一个入度（来自 $(u-y) \bmod x$ ）和一个出度（来自 $(u+y) \bmod x$ ），因此整个图必然由若干个环构成．并且可以证明共有 $\gcd(x,y)$ 个等长的环．

证明

设 $d=\gcd(x,y)$ ，设 $x=da,y=db$ ，有 $\gcd(a,b)=1$ ．

考虑从 $u$ 出发走 $k$ 步，到达 $(u+ky) \bmod x$ ．若成环，则 $ky \equiv 0 \pmod x$ ，即有 $kb \equiv 0 \pmod a$ ．

由于 $\gcd(a,b)=1$ ，最小的 $k=a$ ，即环长为 $a = \dfrac{x}{d}$ ．由于是从任意点开始，故每个可能的环长相等，环的数量为 $d$ ．

并且，边权为正，绕环两圈后，一定不能继续松弛．直接循环更新一遍就行了．这样处理就不会受限于最短路的复杂度，可以做到 $O(x)$ ．

与差分约束问题相同，当存在一组解 $\{a_1,a_2,\cdots,a_n\}$ 时， $\{a_1+d,a_2+d,\cdots,a_n+d\}$ 同样为一组解，因此在该题让 $i=1$ 作为源点，此时源点处的 $dis_{1}=1$ 在已知范围内最小，因此得到的也是一组最小的解．

答案即为：

\sum_{i=0}^{x-1}\left(\frac{h-d_i}{x} + 1\right)

加 1 是由于 $d_i$ 所在楼层也算一次．

代码实现上注意到 $h$ 的范围是 $h \leq 2^{63}-1$ ，所以在求解最短路之前 $d_i$ 的初始值应至少设为 $2^{63}$ ，这超过了 C++ 中 long long 的最大值．所以可以使用 unsigned long long 或者先把 $h \gets h - 1$ ，然后把最低楼层设为 $0$ 层，其他代码无异．

基于环优化的实现

#include <algorithm>
#include <climits>
#include <cstring>
#include <iostream>
#include <vector>

using ll = long long;

constexpr int maxn = 1e5 + 100;

ll d[maxn];
bool vis[maxn];
ll ans;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

void upd(int step, int M) {
  int D = gcd(step, M);
  int len = M / D;

  for (int st = 0; st < D; st++) {
    if (vis[st]) continue;
    std::vector<int> v;
    int u = st;
    for (int i = 0; i < len; i++) {
      v.push_back(u);
      vis[u] = true;
      u = (u + step) % M;
    }
    for (int r = 0; r < 2; r++) {
      for (int i = 0; i < len; i++) {
        int las = v[i];
        int now = v[(i + 1) % len];
        if (d[las] != LLONG_MAX) {
          // 如果d[las]=LLONG_MAX，d[las]+step会越界，需要特判
          d[now] = std::min(d[now], d[las] + step);
        }
      }
    }
  }
}

int main() {
  ll h;
  std::cin >> h;
  int x[3];
  for (int i = 0; i < 3; i++) {
    std::cin >> x[i];
  }
  std::sort(x, x + 3);
  int M = x[0];

  for (int i = 0; i < M; i++) {
    d[i] = LLONG_MAX;
    // 本题的h达到了ll的上界，如果使用ll的话必需把初值置为LLONG_MAX
  }
  d[0] = 0;

  upd(x[1], M);
  memset(vis, 0, sizeof(vis));
  upd(x[2], M);

  ll H = h - 1;
  ans = 0;
  for (int i = 0; i < M; i++) {
    if (d[i] <= H && d[i] != LLONG_MAX) {
      ans += (H - d[i]) / M + 1;
    }
  }
  printf("%lld\n", ans);
  return 0;
}

例题二

ARC084B Small Multiple

题目大意：给定 $n$ ，求 $n$ 的倍数中，数位和最小的那一个的数位和．（ $1\le n\le 10^5$ ）

本题可以使用循环卷积优化完全背包在 $O(n\log^2 n)$ 的时间内解决，但我们希望得到线性的算法．

观察到任意一个正整数都可以从 $1$ 开始，按照某种顺序执行乘 $10$ 、加 $1$ 的操作，最终得到，而其中加 $1$ 操作的次数就是这个数的数位和．这提示我们使用最短路．

对于所有 $0\le k\le n-1$ ，从 $k$ 向 $10k$ 连边权为 $0$ 的边；从 $k$ 向 $k+1$ 连边权为 $1$ 的边．（点的编号均在模 $n$ 意义下）

每个 $n$ 的倍数在这个图中都对应了 $1$ 号点到 $0$ 号点的一条路径，求出 $1$ 到 $0$ 的最短路即可．某些路径不合法（如连续走了 $10$ 条边权为 $1$ 的边），但这些路径产生的答案一定不优，不影响答案．

时间复杂度 $O(n)$ ．

习题

AGC057D - Sum Avoidance

「THUPC 2023 初赛」背包