Reincarnation

正因为梦易碎，才格外美好。

同余最短路

发表于 更新于 分类于 ，
本文字数： 27k 阅读时长 ≈ 25 分钟

“风筝系于九层塔，情人别于万里梦。”

同余最短路

同余最短路本质上不算是图论，更像是通过图论的方式解决数论的问题，同余最短路的解决问题就是求解有多少权值能够通过若干个元素进行非负系数的线性组合的计数问题。

例题

题目简介

题目名称：墨墨的等式
题目来源：国家集训队
评测链接：https://www.luogu.com.cn/problem/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
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
// ----- Eternally question-----
// Problem: P2371 [国家集训队] 墨墨的等式
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2371
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-23 19:09:44
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
const int Inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,a[MAXN];
ll f[MAXN],ql,qr,ans;
bool Vis[MAXN];
inline void Spfa()
{
	std::queue<int>Q;Q.push(0);f[0]=0;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		Vis[u]=0;
		for(int i=2;i<=N;++i)
		{
			int v=(u+a[i])%a[1];
			ll d=f[u]+a[i];
			if(d<f[v])
			{
				f[v]=d;
				if(!Vis[v]) Vis[v]=1,Q.push(v);
			}
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,ql,qr);
	for(int i=1;i<=N;++i) read(a[i]);
	std::memset(f,0x3f,sizeof(f));
	std::sort(a+1,a+N+1);
	Spfa();
	for(int i=0;i<a[1];++i)
	{
		if(qr>=f[i]) ans+=std::max(0ll,(qr-f[i])/a[1]+1);
		if(ql>f[i]) ans-=std::max(0ll,(ql-1-f[i])/a[1]+1);
	}
	write(ans);
	return 0;
}
/*

*/

同余最短路的转圈优化

你发现同余最短路本质上是一个神秘的完全背包，然后转化成了一个较好做的图论模型，那我们可以直接把模型给拆了，不考虑图论与最短路，从本质入手，直接解决这个神秘的完全背包问题。

也就是解决本质上的体积模 的完全背包问题。

在下文中解决那道叫「背包」的问题的时候，我们用到了一点贪心的技巧，首先选择出了性价比 （价值与体积之比）最高的物品作为「基准」（），然后对其余物品作模 的同余最短路，连接体积计算权值。但在那道题中我们也意识到了最短路的弊端，那就是 无法求解最长路，而 时间复杂度错误。

考虑对于 ，每选 个就会使得同余系不变，这意味着我们用 的代价替换掉了一个 ，而对于这两种选择，他们占用了同等的体积，按照贪心思路，因为 的性价比最高，所以肯定会趋向选择 。

因此，对于所有「非基准」物品，每一个最多选 个，所以我们考虑绕着这个长度为 的环转移 圈，因为这样可以保证不漏掉任何状态，且最优，因为如果超过 圈的话说明有负环。如果只转移 圈的话，则需要从初始权值最小的那个点开始转移，实现略显麻烦，相比之下，直接写十分简洁。

对于上面的例题，我们有下面的写法：

参考实现
 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
// ----- Eternally question-----
// Problem: P2371 [国家集训队] 墨墨的等式
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2371
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-24 15:00:27
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
int N,v[MAXN];
ll ql,qr,f[MAXN];
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,ql,qr);
	for(int i=1;i<=N;++i) read(v[i]);
	std::sort(v+1,v+N+1);
	std::memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=2;i<=N;++i)
	{
		int d=gcd(v[i],v[1]);
		for(int j=0;j<d;++j)
			for(int u=j,c=0;c<2;c+=u==j)
			{
				int x=(u+v[i])%v[1];
				checkMin(f[x],f[u]+v[i]);
				u=x;
			}
	}
	ll ans=0;
	for(int i=0;i<v[1];++i)
	{
		if(f[i]<=qr) ans+=std::max(0ll,(qr-f[i])/v[1]+1);
		if(f[i]<ql) ans-=std::max(0ll,(ql-1-f[i])/v[1]+1);
	}
	write(ans);
	return 0;
}
/*

*/

说是优化其实算不上，这个算法实现的时间复杂度是稳定的 ，比起最短路的 看起来快了不少，但实际上在一些不算特意构造的数据面前，肯定是没有 跑得快的，但如果遇到了，那你就赚麻了。

例题

同余最短路计数

题目简介

题目名称：跳楼机
题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P3403

形式化题意：给定 ，求 中有多少个 能够被表示为 ，其中 为非负整数。

数据范围：

考虑直接按照同余最短路的方法开做，设 ，那么连边 。

这道题最离谱的应该是这个 的范围，因为卡着 long long 的上界所以要谨慎选择 的 值，这里考虑首先将 自减 后设 即可。还有一个方法是设 特判，但笔者没成功，不知道行不行。

AC Code
 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// ----- Eternally question-----
// Problem: P3403 跳楼机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3403
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-24 07:56:20
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
typedef unsigned long long ull;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=3e5+10;
const ll INF=9223372036854775807ll;
ll H;
int a,b,c;
struct G
{ int next,to,val; }Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
ll f[MAXN];
bool Vis[MAXN];
void Spfa()
{
	std::queue<int>Q;
	for(int i=0;i<a;++i) f[i]=INF;
	Q.push(0),f[0]=0;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		Vis[u]=0;
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			v=Edge[e].to;
			if(checkMin(f[(v=Edge[e].to)],f[u]+Edge[e].val)) if(!Vis[v]) Q.push(v),Vis[v]=1;
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(H,a,b,c);--H;
	int tmp[3]={a,b,c};
	std::sort(tmp,tmp+3);
	a=tmp[0],b=tmp[1],c=tmp[2];
	for(int i=0;i<a;++i)
	{
		addEdge(i,(i+b)%a,b),
		addEdge(i,(i+c)%a,c);
	}
	ll ans=0;
	Spfa();
	for(int i=0;i<a;++i) if(f[i]<=H) ans+=std::max(0ll,(H-f[i])/a+1);
	write(ans);
	return 0;
}
/*

*/

同余最短路求最值

题目简介

题目名称：牛场围栏
题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P2662

形式化题意：给定 个数 ，你可以使用 之间的任意整数 。求出无法被表示为 ，其中 为非负整数的最大值。

数据范围：

考虑同余最短路，因为 表示同余类为 的最小能被表示的数，那么 就是最大不能被表示的数了，所以我们只需要对所有同余类中的 执行 就可以了。

点数是 的，所以时间复杂度是 。

AC Code
 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// ----- Eternally question-----
// Problem: P2662 牛场围栏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2662
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-24 09:40:55
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e2+10,MAXM=3e3+10,MAXL=3e3+10,MAXS=3e5+10;
const int INF=0x3f3f3f3f;
int N,M,Siz;
std::vector<int>a;
struct G
{ int next,to,val; }Edge[MAXS<<1];
int Head[MAXS],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
int Dist[MAXL];
bool Vis[MAXL];
inline void Spfa()
{
	std::queue<int>Q;
	std::memset(Dist,0x3f,sizeof(Dist));
	Q.push(0),Dist[0]=0;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		Vis[u]=0;
		for(int i=1;i<=Siz;++i)
		{
			int v=(u+a[i])%a[0];
			if(checkMin(Dist[v],Dist[u]+a[i]))
				if(!Vis[v]) Q.push(v),Vis[v]=1;
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1,x;i<=N;++i)
	{
		read(x);
		for(int j=0;j<=M&&x-j>=1;++j) a.push_back(x-j);
	}
	std::sort(a.begin(),a.end());
	a.erase(std::unique(a.begin(),a.end()),a.end());
	Siz=a.size()-1;
	Spfa();
	int ans=-1;
	for(int i=0;i<a[0];++i) checkMax(ans,Dist[i]-a[0]);
	write(ans);
	return 0;
}
/*

*/

同余最短路求最值 II

题目简介

题目名称：

题目来源：

评测链接：https://atcoder.jp/contests/abc077/tasks/arc084_b

形式化题意：求 ，其中 为正整数，并最小化 的数位和。

数据范围：

考虑对同余函数进行变种，设 为模 余 的同余系中的最小数位和。那显然答案就是 ，然后考虑怎么求解。

对于一个数 ，一定可以通过 进行若干次操作 或者 得到，而每一次 会使数位和 ，而 不会改变数位和。

那我们就直接连边 ，然后同余最短路。

那如果涉及到 进位呢？容易发现，如果 要进位，则至少会走过第一种边 次，代价也 ，而此时如果走第二种边的代价是 ，那走哪边就很显然了。

并不是没有错误情况，只是保证了错误的情况都不会被取到。

AC Code
 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
// ----- Eternally question-----
// Problem: D - Small Multiple
// Contest: AtCoder - AtCoder Beginner Contest 077
// URL: https://atcoder.jp/contests/abc077/tasks/arc084_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-07-24 10:10:59
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int K;
struct G
{ int next,to,val; }Edge[MAXN<<2];
int Head[MAXN],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
int Dist[MAXN];
bool Vis[MAXN];
inline void Spfa()
{
	std::queue<int>Q;
	std::memset(Dist,0x3f,sizeof(Dist));
	Dist[1]=1,Q.push(1);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		Vis[u]=0;
		for(int e=Head[u],v;e;e=Edge[e].next)
		{
			if(checkMin(Dist[(v=Edge[e].to)],Dist[u]+Edge[e].val))
				if(!Vis[v]) Q.push(v),Vis[v]=1;
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(K);
	for(int i=1;i<K;++i) addEdge(i,(i+1)%K,1),addEdge(i,i*10%K,0);
	Spfa();
	write(Dist[0]);
	return 0;
}
/*

*/

同余最短路与完全背包

题目简介

题目名称：背包
题目来源： 初赛

评测链接：https://www.luogu.com.cn/problem/P9140

形式化题意：给定 种物品，体积为 ，价值为 ，每种物品有无数个。共 次询问，每次询问背包大小 ，求刚好塞满背包的最大价值，可能无解。

数据范围：

考虑贡献是一个二元组，不算很好求。我们将性价比 最大的那个物品取出来，然后尝试用其它物品塞出一个体积 使得 ，那很显然就是一个同余最短路的形式了。

但贡献依然是一个二元组，考虑压缩成一维。设 为性价比最高的。

对于当前状态 ，以及转移状态 ，如果 ，那么我们会少选一个 ，否则对后面选 不会产生影响，但却选择了一个 ，因此，转移函数可以写成：

然后 即可。也就是跑最长路。

注意到全部选 肯定是最优的，所以这里的 实际上就是在模 余 时需要舍去的最小代价。

我还是第一次知道 居然没有办法跑最长路，所以只能用 ，需要注意的是，这道题 能过，但是过不了评论区里的 ，正确做法应该是转圈优化。

Spfa已经死了
 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
// ----- Eternally question-----
// Problem: P9140 [THUPC 2023 初赛] 背包
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9140
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-24 10:35:30
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=60,MAXV=1e5+10,MAXC=5e6+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int N,Q;
struct Item
{ int v,c; }It[MAXN],Dist[MAXV];
inline bool cmp(Item a,Item b){ return (ll)a.c*b.v>(ll)a.v*b.c; }
struct G
{int next,to,val; }Edge[MAXC<<1];
int Head[MAXV],Total;
inline void addEdge(int u,int v,int w)
{
	Edge[++Total]=(G){Head[u],v,w};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u,w};Head[v]=Total;
}
ll f[MAXV];
bool Vis[MAXV];
struct Node
{
	int now;ll f;
	Node(int now=0,ll f=0):now(now),f(f){}
	bool operator<(const Node &x) const { return f<x.f; }
};
int V,C;
inline void Dijkstra()
{
	std::priority_queue<Node>Q;
	std::memset(f,-0x3f,sizeof(f));
	Q.push(Node(0,0)),f[0]=0;
	while(!Q.empty())
	{
		int u=Q.top().now;Q.pop();
		if(Vis[u]) continue;
		Vis[u]=1;
		for(int i=2;i<=N;++i)
		{
			int v=(u+It[i].v)%V;
			if(checkMax(f[v],f[u]+It[i].c-((ll)(u+It[i].v)/V*C))) Q.push(Node(v,f[v]));
		}
	}
}
inline void Spfa()
{
	std::queue<int>Q;
	std::memset(f,-0x3f,sizeof(f));
	Q.push(0),f[0]=0;
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		Vis[u]=0;
		for(int i=2;i<=N;++i)
		{
			int v=(u+It[i].v)%V;
			if(checkMax(f[v],f[u]+It[i].c-((ll)(u+It[i].v)/V*C))) if(!Vis[v]) Q.push(v),Vis[v]=1;
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(It[i].v,It[i].c);
	std::sort(It+1,It+N+1,cmp);
	V=It[1].v,C=It[1].c;
	Spfa();
	for(ll qV;Q--;)
	{
		read(qV);
		if(f[qV%V]<=-1e17) puts("-1");
		else write(f[qV%V]+qV/V*C,'\n');
	}
	return 0;
}
/*

*/
转圈优化
 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// ----- Eternally question-----
// Problem: P9140 [THUPC 2023 初赛] 背包
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P9140
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-24 15:11:10
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
const ll INF=1e16;
int N,Q;
struct Item
{ int v,c; }It[MAXN];
inline bool cmp(Item a,Item b){ return (ll)a.c*b.v>(ll)a.v*b.c; }
int gcd(int a,int b){ return !b?a:gcd(b,a%b); }
ll f[MAXN];
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,Q);
	for(int i=1;i<=N;++i) read(It[i].v,It[i].c);
	std::sort(It+1,It+N+1,cmp);
	int Vm=It[1].v,Cm=It[1].c;
	std::memset(f,-0x3f,sizeof(f));
	f[0]=0;
	for(int i=2;i<=N;++i)
	{
		int d=gcd(It[i].v,Vm);
		for(int j=0;j<d;++j)
			for(int u=j,c=0;c<2;c+=u==j)
			{
				int v=(u+It[i].v)%Vm;
				checkMax(f[v],f[u]+It[i].c-(ll)(u+It[i].v)/Vm*Cm);
				u=v;
			}
	}
	for(ll qV;Q--;)
	{
		read(qV);
		if(f[qV%Vm]<=-INF) puts("-1");
		else write(f[qV%Vm]+(ll)qV/Vm*Cm,'\n');
	}
	return 0;
}
/*

*/

同余最短路的单调队列优化

题目简介

题目名称：论战捆竹竿
题目来源：

评测链接 ：https://uoj.ac/problem/172
评测链接 ：https://www.luogu.com.cn/problem/P4156

形式化题意：给定无数个相同的长度为 的字符串 ，初始有一个空串 ，每次将一个 插入到 的结尾，且 的前缀和 的后缀部分如果相同则可以合并，如 ，则新串可以是 ，求长度在 的串个数。多测。

数据范围：

考虑可以合并的部分其实就是 的 ，设 的 集合为 ，那么每插入一个 ， 的长度变化就是 ，然后就很显然了，题目直接转化为，有多少个 ，能够被表示为 ，其中 为非负整数。

我们只需要 通过 求出 的所有 后，就是一个同余最短路的形式了。

但容易发现，你不管 ，还是跑圈，时间复杂度都不会低于 ，这显然是做不了的。考虑突破这个限制，观察规律。

和 有一个较为重要的性质，那就是一个字符串的所有 构成至多 个等差数列。这一个性质我们会在失配树中详细提到。

我们每次提出其中一个等差数列单独维护，对于一个等差数列 ，我们取 的同余系，那么最后会维护 个独立的环，而等差数列之间相互独立，如果直接枚举转移会导致时间复杂度回到 ，所以不能直接枚举环。

按照前面的思路，我们在环上找到最小的 作为转移的起点，然后通过前面的转圈优化逐步转移，且相邻点的转移都为 ，所以，很巧妙地，这个过程是可以通过单调队列维护的。

在队列中维护极距离不超过 （等差数列长度）的值，并更新 为单调阈值。依次维护。

然后考虑等差数列之间的维护，涉及到切换模数，考虑和环一样做，依然维护一个队列即可，因为没有 的限制，所以不要求单调。注意如果一个等差数列只有一项的话，就把 转移即可。

时间复杂度 。

AC Code
 
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// ----- Eternally question-----
// Problem: P4156 [WC2016] 论战捆竹竿
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4156
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-07-24 15:58:06
// ----- Endless solution-------

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e5+10;
const ll INF=0x3f3f3f3f3f3f3f3f;
int Test,N;
ll W,lim;
char Str[MAXN];
int Kmp[MAXN],Bor[MAXN],Cnt;
ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b); }
inline void getKmp(char *s,int n)
{
	int j=0;Cnt=0;
	for(int i=2;i<=n;++i)
	{
		while(j&&s[i]!=s[j+1]) j=Kmp[j];
		if(s[i]==s[j+1]) ++j;
		Kmp[i]=j;
	}
	while(j) Bor[++Cnt]=n-j,j=Kmp[j];
	Bor[++Cnt]=n;
}
ll f[MAXN<<3],g[MAXN<<3];
int Top,Head,Tail;
int Q[MAXN<<3],Qe[MAXN<<3];
inline void remod(int len)
{
	int gc=gcd(lim,len);
	for(int i=0;i<lim;++i) g[i]=f[i];
	for(int i=0;i<len;++i) f[i]=INF;
	for(int i=0;i<lim;++i)
	{
		ll tmp=g[i]%len;
		checkMin(f[tmp],g[i]);
	}
	for(int i=0;i<gc;++i)
	{
		Top=0;Q[++Top]=i;
		ll v=(i+lim)%len;
		while(v!=i){ Q[++Top]=v;v=(v+lim)%len; }
		for(int j=Top+1;j<=Top*2;++j) Q[j]=Q[j-Top];
		for(int j=2;j<=(Top<<1);++j) checkMin(f[Q[j]],f[Q[j-1]]+lim);
	}
	lim=len;
}
void modify(ll x,ll d,ll len)
{
	if(d<0) return ;
	int gc=gcd(lim,d);
	for(int i=0;i<gc;++i)
	{
		Top=0;Q[++Top]=i;
		ll tmp=(i+d)%lim;
		while(tmp!=i){ Q[++Top]=tmp;tmp=(tmp+d)%lim; }
		tmp=1;
		for(int j=2;j<=Top;++j) if(f[Q[j]]<f[Q[tmp]]) tmp=j;
		for(int j=1;j<=Top;++j) g[j]=Q[j];
		for(int j=tmp;j<=Top;++j) Q[j-tmp+1]=g[j];
		for(int j=1;j<tmp;++j) Q[j+(Top-tmp+1)]=g[j];
		Head=Tail=1,Qe[1]=1;
		for(int j=2;j<=Top;++j)
		{
			while(Head<=Tail&&j-Qe[Head]>len) ++Head;
			checkMin(f[Q[j]],f[Q[Qe[Head]]]+x+d*(j-Qe[Head]));
			while(Head<=Tail&&f[Q[Qe[Tail]]]+d*(j-Qe[Head])>f[Q[j]]) --Tail;
			Qe[++Tail]=j;
		}
	}
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N,W),scanf("%s",Str+1);
		if(W<N){ puts("0");continue; }
		getKmp(Str,N);
		W-=N,f[0]=0,lim=N;
		int l=1;
		while(l<=Cnt)
		{
			int r=l;
			while(Bor[r+1]-Bor[r]==Bor[l+1]-Bor[l]) ++r;
			remod(Bor[l]);
			if(r>Cnt){ l=r;continue; }
			modify(Bor[l],(l==r?0:Bor[l+1]-Bor[l]),r-l);
			l=r;
		}
		ll ans=0;
		for(int i=0;i<lim;++i)
		{
			if(W<f[i]) continue;
			ans+=(W-f[i])/lim+1;
		}
		write(ans,'\n');
		for(int i=0;i<N;++i) f[i]=INF;
	}
	return 0;
}
/*

*/
相关文章