MinamiMelon
0%

同余最短路问题

发表于 更新于

有多少整数\(b\in [0,h)\),使得\(\sum\limits_{i=1}^{n}a_ix_i=b\)有非负整数解。

令\(dis_i\)表示最小的符合\((\sum\limits_{i=1}^{n}a_ix_i)\space mod\space a_k=i(\forall k \in[1.n])\)的\(\sum\limits_{i=1}^{n}a_ix_i\), 则\(i+t\cdot a_k,\forall t \in \mathbb{N}\)都有解。

\(\forall i \in [0,a_k)\),\(\forall j\in[1,n],j\neq k\)建边\((i,(i+a_j)mod\space a_k)\),边权为\(a_j\), 从0开始跑最短路可求\(dis_i\),\(a_k\)取\(a_1...a_n\)中最小的可保证建边最少运行最快。

\[ ans=\sum\limits_{i=1}^{n}(\lfloor\frac{h-dis_i}{a_k}\rfloor+1) \]

Luogu P3403 跳楼机

题意为: 给定 h,x,y,z，对于 k∈[1,h]，有多少个 k 满足 ax+by+cz=k

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
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int cnt,hd[N];
struct Edge{
	int t,v,n;
}e[N*20];
typedef long long ll;
void build(int f,int t,int v){
	e[++cnt]=(Edge){t,v,hd[f]};
	hd[f]=cnt;
}
queue<int> q;
bool inq[N];
ll dis[N];
int main(){
	ll h,x,y,z;
	scanf("%lld%lld%lld%lld",&h,&x,&y,&z);
	--h;
	for(int i=0;i<x;++i){
		build(i,(i+y)%x,y);
		build(i,(i+z)%x,z);
	}
	for(int i=0;i<N;++i){
		dis[i]=2e18;
	}
	q.push(0);
	dis[0]=0;
	inq[0]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=hd[u];i;i=e[i].n){
			int v=e[i].t;
			if(dis[v]>dis[u]+e[i].v){
				dis[v]=dis[u]+e[i].v;
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	unsigned long long ans=0;
	for(int i=0;i<x;++i){
		if(dis[i]<=h)
			ans+=(h-dis[i])/x+1;
	}
	printf("%llu\n",ans);
	return 0;
}

墨墨突然对等式很感兴趣，他正在研究 \(\sum_{i=1}^n a_ix_i=b\)存在非负整数解的条件，他要求你编写一个程序，给定 \(n, a_{1\dots n}, l, r\),求出有多少\(b\in[l,r]\)可以使等式存在非负整数解。

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
62
63
64
65
66
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+5;
int cnt,hd[N];
struct Edge{
	int t,v,n;
}e[N*24];
typedef long long ll;
void build(int f,int t,int v){
	e[++cnt]=(Edge){t,v,hd[f]};
	hd[f]=cnt;
}
queue<int> q;
bool inq[N];
ll dis[N],a[20];
int main(){
	ll n,l,r;
	scanf("%lld%lld%lld",&n,&l,&r);
	l--;
	ll mn=1e18,k=-1;
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
		if(a[i]<mn){
			k=i;
			mn=a[i];
		}
	}
	for(int i=0;i<mn;++i){
		for(int j=1;j<=n;++j){
			if(j!=k){
				build(i,(i+a[j])%mn,a[j]);
			}
		}
	}
	for(int i=0;i<N;++i){dis[i]=2e18;}
	q.push(0);
	dis[0]=0;
	inq[0]=1;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		inq[u]=0;
		for(int i=hd[u];i;i=e[i].n){
			int v=e[i].t;
			if(dis[v]>dis[u]+e[i].v){
				dis[v]=dis[u]+e[i].v;
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	unsigned long long al=0,ar=0;
	for(int i=0;i<mn;++i){
		if(dis[i]<=r){
			ar+=(r-dis[i])/mn+1;
			if(dis[i]<=l){
				al+=(l-dis[i])/mn+1;
			}
		}
	}
	printf("%llu\n",ar-al);
	return 0;
}