0. 前言

本篇文章不发布于洛谷文章广场，因为我是在自己 yy，不保证正确。

1. 介绍

同余最短路，用于解决完全背包计数问题，例如给你nn 个数，每个数可以选无限次，问你用这些数能够拼凑出的信息。

这里我们一般化，给定物品体积aa，每个物品可以选无数次，问是否存在一种选择方式，使得物品总体积恰好为xx。

考虑 DP，设f(i)f(i) 表示能否拼凑出体积xx，转移方程是显然的：

f(x)=f(x)or⁡f(x−ai)f(x)=f(x) \operatorname{or} f(x-a_{i})

这是一个有向无环图（DAG）上的动态规划，没有环，这样的时间复杂度是非常高，因为我们要枚举xx，当xx 非常大的时候是无法承受。

而同余最短路就是优化这一过程的，首先对于一个完全背包计数问题，如果xx 可以被凑出来，那么x+ai,x+2ai,…x+a_{i},x+2a_{i},\dots 是可以都能够凑出来的。即如果能凑出来xx，那么x+k×ai(k≥0)x+k\times a_{i} (k\ge 0) 是可以凑出的。

我们可以这样，我们设定一个基准物品mm，令mm 为它的体积。前面我们提到了这种凑的方案，考虑用基准物品表示这些。

我们用基准物品去表示，所有kmkm 的都会被标记，最终xx 序列会剩下这样的集合没有被标记：{x+km∣x∈[0,m−1],k∈N}\left\{ x+km | x\in [0,m-1],k \in \mathbb{N}\right\}。那这些怎么处理呢？我们有一个思路，我们不妨设disidis_{i} 表示ii 最小能够表示的数，那么所有更大的disi+kmdis_{i}+km 是可以标记，也就是说我们只需要求出最小标记的数即可，那么现在问题缩小到了x∈[0,m−1]x\in [0,m-1] 的范围内，也就是mm 下的剩余类。

上面说这么多的话，只涉及到基准物品的刻画，但是其他的物品你可是一点都没有考虑！别急，我们现在就考虑这些物品带来的贡献，考虑现在我们需要求什么，我们需要求disidis_{i} 即ii 最小能够表示的数。这个时候我们就可以考虑aia_{i} 这个跳板，我们利用这个跳板来求解disidis_{i}，对于每个其他物品 aia_{i}，尝试将其加到当前已覆盖的数上，从而扩展剩余类的可表示范围。

具体的，对于每个u∈[0,m−1]u\in[0,m-1]，计算v=(u+ai) mod mv=(u+a_{i})\bmod m（更新disdis 的i∈[0,m−1]i\in[0,m-1]），并更新：

disv=min⁡(disv,disu+ai)dis_{v}=\min (dis_{v},dis_{u}+a_{i})

即若已知x≡u(modm)x \equiv u \pmod m 的最小可表述数是disudis_{u}，那么x+ai≡v(modm)x+a_{i} \equiv v \pmod m 也是一个可表示数，且可能成为vv 的更优解。

细心的读者可能已经发现这不就是最短路的形式吗！没错我们可以这么刻画，u→(u+ai) mod mu \to (u+a_{i})\bmod m 连边，边权aia_{i}，因为没有负边权我们可以跑 Dijkstra 或 SPFA即可。

其实我们上述变化的本质，就是们钦定一个基准物品，现在我们有了基准物品所构成一个取数集合，让后让其他物品在基准物品上拓宽这个集合的选取范围，上述的最短路过程相当于就是过动态松弛，逐步探索如何组合不同的 aia_{i}​ 来覆盖所有剩余类。最短路径长度 disrdis_{r} 给出了每个剩余类的最小可表示数，对应原问题就是可以将两次经过同一个点之间添加的所有物品换成若干基准物品。所以，我们可以将完全背包转化为类多重背包问题，从而解决了完全背包的计数问题。

至于类多重背包的解释就是：完全背包的 “无限” 选择被限制。-在同余最短路中，由于剩余类的周期性和最短路的最优性，每个物品 aia_{i} 在实际转移过程中最多使用有限次。如果在最短路中，某个物品 aia_{i}​ 被多次使用（例如两次经过同一个剩余类），则中间的部分可以替换为若干基准物品 mm。

一般的，我们基准物品mm 取m=∑i=1naim=\sum\limits_{i=1}^n a_{i}。这样能保证点数尽量小，选取其他也是可以的。

同余最短路的本质：就是从完全背包的 DP 到模意义下的最短路。

2. 一些例题

P3403 跳楼机

显然操作 4 没有任何卵用，其实就是上面的问题板子，这里给出上面的一种实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define int long long
#include <float.h>
#define pir pair<int,int>
using namespace std;
constexpr int MN=1e5+15;
struct Edge{
    int v,w;
};
int x,y,z,dis[MN],h;
vector<Edge> adj[MN];
bool vis[MN];

void dij(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<pir,vector<pir>,greater<pir>> q;
    q.push(pir(0,0));
    dis[0]=0;
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto e:adj[u]){
            if(dis[e.v]>dis[u]+e.w){
                dis[e.v]=dis[u]+e.w;
                q.push({dis[e.v],e.v});
            }
        }
    }
}

signed main(){
    cin>>h>>x>>y>>z;
    if(x==1||y==1||z==1){
        cout<<h;
        return 0;
    }
    h--;//注意从 0 开始
    for(int i=0;i<x;i++){
        adj[i].push_back({(i+y)%x,y});
        adj[i].push_back({(i+z)%x,z});
    }
    dij();
    int ans=0;
    for(int i=0;i<x;i++){
        if(dis[i]<=h) ans+=(h-dis[i])/x+1; //计算贡献
    }
    cout<<ans;
    return 0;
}

P2371 [国家集训队] 墨墨的等式

将询问差分，现在问题转化为求[1,n][1,n] 的问题，这个问题其实和上面是一个问题，只不过从n=3n=3 拓展了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
#define int long long
#include <float.h>
#define pir pair<int,int>
using namespace std;
constexpr int MN=6e5+15;
struct Edge{
    int v,w;
};
int n,ans1,ans2,fz=-1,a[MN],dis[MN],l,r;
vector<Edge> adj[MN];
bool vis[MN];

void dij(){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<pir,vector<pir>,greater<pir>> q;
    q.push(pir(0,0));
    dis[0]=0;
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(auto e:adj[u]){
            if(dis[e.v]>dis[u]+e.w){
                dis[e.v]=dis[u]+e.w;
                q.push({dis[e.v],e.v});
            }
        }
    }
}

signed main(){
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]==1){
            cout<<r-l+1;
            return 0;
        }
        if(a[i]!=0&&fz==-1) fz=i;
    }
    if(fz==-1){
        cout<<0;
        return 0;
    }
    for(int i=0;i<a[fz];i++){
        for(int j=1;j<=n;j++){
            adj[i].push_back({(i+a[j])%a[1],a[j]});
        }
    }
    dij();
    l--;
    for(int i=0;i<a[fz];i++){
        if(dis[i]<=r) ans1+=((r-dis[i])/a[fz]+1);
        if(dis[i]<=l) ans2+=(l-dis[i])/a[fz]+1;
    }
    cout<<ans1-ans2;
    return 0;
}

3. 最短路优化

最短路的时间复杂度有的时候比较高，不能承受，我们考虑能不能给他优化一下。

我们考虑，一个物品aia_{i} 最多用几次就没有意义了，你可能认为是ai−1a_{i}-1，对也不对。其实更好的上限应该是aigcd⁡(ai,m)−1\dfrac{a_{i}}{\gcd(a_{i},m)}-1，也就是说用aigcd⁡(ai,m)\dfrac{a_{i}}{\gcd(a_{i},m)} 次就会出现aia_{i} 的倍数，为什么？

kai mod m=0m∣kai\begin{aligned} ka_{i} \bmod m & =0 \\ m & | ka_{i} \end{aligned}

不妨设g=gcd⁡(ai,m)g=\gcd(a_{i},m)，那么有：

gn∣kgm,gcd(n,m)=1n∣km∵gcd(n,m)=1∴n∣k\begin{aligned} gn|kgm,gcd(n,m) &=1 \\ n | km \\ \because gcd(n,m)=1 \\ \therefore n|k \end{aligned}

所以kk 最小取值就是nn，即aigcd⁡(ai,m)\dfrac{a_{i}}{\gcd(a_{i},m)}。于是我们就可以涉及转移啦，这里借用 同余最短路 林晋堃 的图：

image.png

不难发现转移呈环状，考虑从这个环下手，我们把所有这个物品用的次数中相同余数的点缩成一个点，就变成了这样：

image.png

好像时间复杂度根本就没有任何变化，但是我们注意到前面的结论，我们从任何一个余数出发原本只能走gcd⁡(m,ai)−1\gcd(m,a_{i})-1 就停了下来，但是转圈法，也就是我们对最短路的优化，就是不要停下来，继续走，那么每个点的状态如下：

image.png

这种转移方式和刚才的转移不太一样，但是因为每个点的答案起码都大于等于 3 了，由于超过 3 就没有用了所以说这个转移方法转移次数不仅更优，而且也不会影响到答案。 这就是——大名鼎鼎的转圈背包！至于为什么叫转圈背包，那是因为这个转移很像在转圈。

总的来说，就是模mm 意义下的完全背包，对于体积为aia_{i} 的物品在长度为mm 的环上生成d=gcd⁡(ai,m)d=\gcd(a_{i},m) 个子环从一个点出发，不可能绕着子环走一圈再转移回到该点，因为最短路不会经过同一个点两次，否则存在负环。如果重复经过同一个点，那么可以将这两次经过之间加入的所有物品替换为若干基准物品。

我们考虑添加aia_{i} 的时候，至多加入mgcd⁡(ai,m)−1\dfrac{m}{\gcd(a_{i},m)}-1 个。对于每个子环，我们绕子环转两圈即可更新到所有答案，若从最小点开始则一即可。

4. 最短路优化例题

P2371 墨墨的等式

来个模板！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=5e5+15;
int n,m,l,r,ans,a[MN],b[MN],f[MN];


signed main(){
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!a[i]) n--,i--;
    }
    if(!n) cout<<0<<'\n',exit(0);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    sort(a+1,a+1+n);
    m=a[1];
    for(int i=1;i<=n;i++){
        b[i]=a[i]%m;
    }
    for(int i=2;i<=n;i++){
        for(int j=0,lim=__gcd(a[i],m);j<lim;j++){
            for(int k=j,c=0;c<2;c+=k==j){
                int p=k+b[i];
                if(p>=m) p-=m;
                f[p]=min(f[p],f[k]+a[i]);
                k=p;
            }
        }
    }
    for(int i=0;i<a[1];i++){
        if(r>=f[i]) ans+=max((r-f[i])/a[1]+1,0ll);
        if(l>f[i]) ans-=max((l-1-f[i])/a[1]+1,0ll);
    }
    cout<<ans;
    return 0;
}

洛谷 P2662 牛场围栏

本质上就是将处理过后的aia_{i} 跑上面的东西，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15;
constexpr int INF=1e18;
int f[MN],a[MN],b[MN],tot,n,m,ans,mod;



signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    mod=max(1ll,a[1]-m);
    if(mod==1){
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++){
        int lst=max(a[i-1]+1,a[i]-m);
        for(int j=lst;j<=a[i];j++){
            if(j!=mod){
                b[++tot]=j;
            }
        }
    }
    sort(b+1,b+1+tot);
    tot=unique(b+1,b+1+tot)-b-1;
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=tot;i++){
        for(int j=0,lim=__gcd(b[i],mod);j<lim;j++){
            for(int cur=j,c=0;c<2;c+=cur==j){
                int nxt=(cur+b[i])%mod;
                f[nxt]=min(f[nxt],f[cur]+b[i]);
                cur=nxt;
            }
        }
    }
    for(int i=0;i<mod;i++){
        if(f[i]>=0x3f3f3f3f3f3f3f3f){
            cout<<-1;
            return 0;
        }
        ans=max(ans,f[i]-mod);
    }
    cout<<ans;
    return 0;
}

「THUPC 2023 初赛」背包

这个题好，有助于我们完全理解同余最短路。

本题在完全背包的可行性基础上加入了权值这一维度。我们上面的题都是把mm 作为aia_{i} 的最小值出现，而这里我们并不是要aia_{i} 的最小值，而是将civi\dfrac{c_{i}}{v_{i}} 最大的物品选座位基准物品，即把性价比最大的物品设置为基准物品。

如果你理解上述的过程，不难发现一个点就是实际上基准物品仍然在标记数字中占贡献的绝大部分，将一部分其它物品替换为若干基准物品，以最大化单位体积贡献的价值。所以如果题目中有限制，那么基准物品的选取将成为关键的地方。

容易发现对于一些总体积为vkv_{k} 的物品不如换为kk，因为kk 是性价比最高的。但是对于总体积vkv_{k} 来说就不一定，最优解可能比全部取kk 并空出剩下容量要优或劣。考虑求出两个背包方案的优劣之分。考虑 DP，设VV 为体积，CC 为价值，设f(i)f(i) 表示i≡V(modvk)i \equiv V \pmod {v_{k}} 下最大的C−⌊Vvk⌋×ckC-\lfloor \dfrac{V}{v_{k}} \rfloor \times c_{k}，也就是最优解比全取kk 优劣多少。有转移：

fi=max⁡j=1nfj+cj−⌊i+vjvk⌋×ckf_{i}=\max_{j=1}^n f_{j}+c_{j}-\lfloor \dfrac{i+v_{j}}{v_{k}} \rfloor \times c_{k}

转移有后效性，考虑跑最长路，这个图是负边权图，可以跑，用转圈时间复杂度O(nm)O(nm)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int MN=1e6+15;
int f[MN],n,q,mv[MN],md[MN],v[MN],d[MN],c[MN],w,m=1;


signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>v[i]>>c[i];
        if(w*v[i]<c[i]*m) w=c[i],m=v[i];
    }
    for(int i=1;i<=n;i++){
        mv[i]=v[i]%m;
        md[i]=v[i]/m;
    }
    for(int i=1;i<m;i++){
        f[i]=-1e18;
    }
    for(int i=1;i<=n;i++){
        for(int j=0,lim=__gcd(v[i],m);j<lim;j++){
            for(int k=j,cy=0;cy<2;cy+=k==j){
                int p=k+mv[i],d=md[i];
                if(p>=m) p-=m,d++;
                f[p]=max(f[p],f[k]+c[i]-d*w);
                k=p;
            }
        }
    }
    for(int i=1;i<=q;i++){
        int V;
        cin>>V;
        int p=V%m;
        if(f[p]<-1e17) cout<<-1<<'\n';
        else cout<<f[p]+V/m*w<<'\n';
    }
    
    return 0;
}

5. 总结

同余最短路，其实就是对于完全背包计数问题的一种解决方案，通过模意义与基准物品的选取优化。

放点同类的题？

ARC084B Small Multiple

「NOIP2018」货币系统