同余最短路学习笔记

今天讲课讲到了同余最短路。简单记一下，防止之后忘了这个坑。

同余最短路 in oiwiki

简介

同余最短路，可以用来处理问题：

1.「给定 n 个数，求这些数能拼出多少其他数（选数数量不限）」

2.「给 n 个数，求这些数不能拼出的最大 or 最小值」

3.「至少拼几次才能拼出模 k 余 x 的数」。

同余最短路可以通过同余来构造状态，类比差分约束的转换思路，利用同余构造的状态可以看做单源最短路中的点。同余最短路的转移通常是：\(f(i+x)=f(i)+x\)，类似于普通最短路中的 \(f(v)=f(u)+d(u,v)\)。

例题1：P3403 跳楼机

首先考虑，如果我只用 \(y\) 和 \(z\) 拼新，即 \(ay+bz = k\)，对于每一个 \(k\)，在我以后处理的过程中，无论加多少个 \(x\)，其唯一不变的是 \(k%x\) 的这个值。

所以考虑对于与余数为 \([0,x)\) 的数，我们实际上只需要保留最小的 \(ay+bz\)，这样才能在后面加 \(x\) 的处理中获得更大的数。

因此考虑，点编号就是余数，不断的往上添加 \(y\) 和 \(z\)，以 \([0,x)\) 为分别边的起点，以 \(f(i+x)=f(i)+x\) 作为转移，新的余数作为边的终点，加上的 \(y\)，\(z\) 作为边权。

对其跑最短路，\(d_i\) 就是同余中的最小 \(k\)。

因为最大限制为 \(h\)，那你从 \(k\) 通过 \(x\) 的倍数最多能翻出来 \(\left \lfloor{ \frac{h-k}{x}}\right \rfloor + 1\)（加一是考虑 \(x\) 的系数为 \(0\)）。答案加起来。

嗯我 \(x\) 写成 \(t\) 是因为两个变量名重了。调了一阵子。感谢机房大佬帮我调。

特别注意当 \(x\) 为 \(1\) 时其模数没有意义，需要特判。

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N=2e5+10;
ll h,ans;
int t,y,z;
priority_queue<pair<ll,int> >q;
int idx,e[N],w[N],nxt[N],head[N];
int vis[N];
ll d[N];
void add(int x,int y,int z){
	e[++idx]=y;
	w[idx]=z;
	nxt[idx]=head[x];
	head[x]=idx;
}
void dij(){
	memset(d,0x3f,sizeof d);
	d[1%t]=1;
	q.push(make_pair(-1,1%t));
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=nxt[i]){
			if(d[e[i]]>d[x]+w[i]){
				d[e[i]]=d[x]+w[i];
				q.push(make_pair(-d[e[i]],e[i]));
			} 
		}
	}
}
int main(){
	scanf("%lld%d%d%d",&h,&t,&y,&z);
	for(int i=0;i<t;i++){
		add(i,(i+y)%t,y);
		add(i,(i+z)%t,z);
	}
	dij();
	for(int i=0;i<t;i++) if(h>=d[i]&&d[i]!=INF) ans+=((h-d[i])/t+1);
	printf("%lld",ans);
}

例题 2：P2371 [国家集训队] 墨墨的等式

做法类比上一题，对于以一个数作为基准建边跑同余最短路，最后对于区间类似前缀和统计。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e6+10;
ll l,r,ans;
ll d[N];
int n;
int vis[N];
int idx,e[N],w[N],nxt[N],head[N];
priority_queue<pair<int,int> > q;
void add(int x,int y,int z){
	e[++idx]=y;
	w[idx]=z;
	nxt[idx]=head[x];
	head[x]=idx;
}
void dij(){
	memset(d,0x3f,sizeof d);
	d[0]=0;
	q.push(make_pair(0,0));
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=nxt[i]){
			if(d[e[i]]>d[x]+w[i]){
				d[e[i]]=d[x]+w[i];
				q.push(make_pair(-d[e[i]],e[i]));
			}
		}
	}
}
int main(){
	int x,y;
	scanf("%d%lld%lld%d",&n,&l,&r,&x);
	for(int i=1;i<n;i++){
		scanf("%d",&y);
		for(int i=0;i<x;i++) add(i,(i+y)%x,y); 
	}
	dij();
	l--;
	for(int i=0;i<x;i++){
		if(r>=d[i]) ans+=(r-d[i])/x+1;
		if(l>=d[i]) ans-=(l-d[i])/x+1;
	}
	printf("%lld",ans);
	return 0;
}

注意这个题，数组需要开 5e6。开大了会 MLE，小了会显示 TLE。别问我怎么知道的。