同余最短路¶
基本思想¶
通过同余构造某些状态，状态之间的关系类似于两点之间的带权有向边。 那么可以以此建图，将某些问题转化为最短路问题，再使用具有优秀时间复杂度的算法求解。
例题 #1 跳楼机¶
题目描述
Srwudi 的家是一幢 \(h\) 层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi 改造了一个跳楼机，使得访客可以更方便的上楼。
经过改造，srwudi 的跳楼机可以采用以下四种方式移动：
-
向上移动 \(x\) 层；
-
向上移动 \(y\) 层；
-
向上移动 \(z\) 层；
-
回到第一层。
一个月黑风高的大中午，DJL 来到了 srwudi 的家，现在他在 srwudi 家的第一层，碰巧跳楼机也在第一层。DJL 想知道，他可以乘坐跳楼机前往的楼层数。
\(1 \le h \le 2^{63}-1\)，\(1 \le x,y,z \le 10^5\)。
首先可以将 \(h\) 减去 \(1\)，同时起始楼层设为 \(0\)。
设 \(d_i\) 为能够到达的最低的 \(\bmod x = i\) 的楼层。我们求出 \(d_i\) 后，对于所有\(d_i+kx\)组成的集合D，可以证明D包含了所有可以到达的楼层。
即我们可以这样考虑：所有可行的路径都是ax+by+cz，其中题目的4操作是没有意义的。于是我们就可以将ax提出，先求出所有可达的by+cz，然后考虑ax。
但是我们也不能求出所有的by+cz，因此为了包含所有的答案，我们只需要对于任意\(i\in[0,x)\)，求出对x取模=i的最小的by+cz即可。
建图：
有 \(i \stackrel{y}{\longrightarrow} (i+y)\bmod x\) 和 \(i \stackrel{z}{\longrightarrow} (i+z)\bmod x\)。 像这样建图后，\(d_i\) 就相当于 \(0 \to i\) 的最短路，Dijkstra 即可。
最后统计时，对于 \(d_i \le h\)，有贡献 \(\lfloor\frac{h-d_i}x\rfloor + 1\)。 总时间复杂度 \(\mathcal O(n \log n)\)。
/*
Keyblinds Guide
###################
@Ntsc 2024
- Ctrl+Alt+G then P : Enter luogu problem details
- Ctrl+Alt+B : Run all cases in CPH
- ctrl+D : choose this and dump to the next
- ctrl+Shift+L : choose all like this
- ctrl+K then ctrl+W: close all
- Alt+la/ra : move mouse to pre/nxt pos'
*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;
#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first
// #define innt int
// #define inr int
// #define mian main
// #define iont int
#define rd read()
int read(){
int xx = 0, ff = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
ff = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
xx = xx * 10 + (ch - '0'), ch = getchar();
return xx * ff;
}
void write(int out) {
if (out < 0)
putchar('-'), out = -out;
if (out > 9)
write(out / 10);
putchar(out % 10 + '0');
}
#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
if constexpr (enable_dbg){
cerr << s;
if(1)cerr<<' ';
if constexpr (sizeof...(Args))
dbg(args...);
}
}
const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
struct node{
int v,w;
};
vector<node> e[N];
int dis[N],vis[N];
int a,b,c;
priority_queue<pii>pq;
void djstr(int s){
for(int i=0;i<=a;i++)dis[i]=INF;
dis[s]=0;
pq.push(mp(0,s));
while(pq.size()){
int x=pq.top().ps;
pq.pop();
if(vis[x])continue;
vis[x]=1;
for(auto v:e[x]){
if(dis[v.v]>dis[x]+v.w){
dis[v.v]=dis[x]+v.w;
pq.push(mp(-dis[v.v],v.v));
}
}
}
}
void add(int a,int b,int c){
e[a].push_back({b,c});
}
void solve(){
int h=rd;
h--;
a=rd,b=rd,c=rd;
for(int i=0;i<a;i++){
add(i,(i+b)%a,b);
add(i,(i+c)%a,c);
}
djstr(0);
int ans=0;
for(int i=0;i<a;i++){
if(dis[i]<=h)ans+=(h-dis[i])/a+1;
}
cout<<ans<<endl;
}
signed main() {
int T=1;
while(T--){
solve();
}
return 0;
}
例题 #2 [国家集训队] 墨墨的等式¶
题目描述
墨墨突然对等式很感兴趣，他正在研究 \(\sum_{i=1}^n a_ix_i=b\) 存在非负整数解的条件，他要求你编写一个程序，给定 \(n, a_{1\dots n}, l, r\)，求出有多少 \(b\in[l,r]\) 可以使等式存在非负整数解。
对于 \(100\%\) 的数据，\(n \le 12\)，\(0 \le a_i \le 5\times 10^5\)，\(1 \le l \le r \le 10^{12}\)。
转化题意
你有n种移动方式，第i种方式可以让你向上走\(a_i\)层，一开始你在0层，求最终可以到达的在[l,r]之间的层数。
思路
首先我们应该想到的是完全背包吧
很容易想到 完全背包，用 \(f_i\) 表示 \(B\) 的值能否为 \(i\)，那么转移方程为 \(\large {f_j = f_j \mid f_{j - a_i}}\)
……但l,r过大，我们不能这样做。
我们可以分别求出 \(0 \sim r\) 中符合条件的 \(B\) 的数量 和 \(0 \sim l - 1\) 中符合条件的 \(B\) 的数量，前者减去后者即是答案。现在假设 \(mn\) 是 \(a_i\) 中的一个数，那么对于 \(a_1x_1 + a_2x_2 + \cdots + a_nx_n = i\) 若该式存在整数解，那么 \(a_1x_1 + a_2x_2 + \cdots + a_nx_n = i + k \times mn\ (k \in \rm N)\) 也都存在整数解。在这个式子中，显然 \(i\) 越小，符合条件的解的数量就会越多。
我们可以用 \(dis_i\) 表示 \(B\) 模 \(mn\) 等于 \(i\) 时的最小值。因为我们的\(a_1x_1 + a_2x_2 + \cdots + a_nx_n = B\)，不妨让mn为 \(a_1\)，参考上面一题的讲解，我们也是只需要对于所有i求出最小的模mn=i的B，然后就可以O(1)计算了。
接下来连有向边 \(i \to (i + a_j) \bmod mn\)，其中 \(0 \leq i < mn\)，边权为 \(a_j\)，表示从 \(i\) 变为 \(i + a_j\) 所花费的代价是 \(a_j\) 。\(0\) 到 \(i\) 的最短路即是 \(B\) 模 \(mn\) 等于 \(i\) 时的最小值。假定现在要求 \(0 \sim x\) 中符合条件的 \(B\) 的数量，若这个最小值不大于 \(x\)，则所有的 \(i + k \times mn\ (i + k \times mn \leq x,k \in \rm N)\) 都符合条件，一共有 \(\left \lfloor \frac{x - dis_i}{mn} \right \rfloor + 1\) 个。
所以枚举 \(i\)，累加就能得到答案。同时 \(mn\) 取所有 \(a_i\) 的最小值最优，因为这样边数最少。时间复杂度为 \(O(kn\max\limits_{i = 1}^n\{ a_i \})\) 。由于特殊的连边，\(\rm SPFA\) 不会被卡，可以放心使用。
Std
/*
CB Ntsc
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mp make_pair
#define pii pair<int,int>
const int N=5e5+5;
const int INF=1e9+5;
const int MOD=998244353;
bool f1;
struct node{
int nxt,dis;
};
vector<node>e[N];
priority_queue<pair<int,int> >pq;
int n,vis[N],dis[N],m,k,s,t;
int mn=INF,l,r,a[N];
bool f2;
#define rd read()
inline int read()
{
int xx=0,ff=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
return xx*ff;
}
inline void write(int out)
{
if(out<0) putchar('-'),out=-out;
if(out>9) write(out/10);
putchar(out%10+'0');
}
void add(int a,int b,int c){
e[a].push_back({b,c});
}
void djstr(int rt) {
pq.push(make_pair(0,rt));
int u=rt; //先从起点开始查
memset(dis,0x3f3f,sizeof dis); //初始化边权
dis[rt]=0;
while(pq.size()) { //搜完全图
u=pq.top().second;
pq.pop();
if(vis[u])continue;//记得continue
vis[u]=1;
for(int i=0;i<e[u].size();i++){
int v=e[u][i].nxt,w=e[u][i].dis;
if(!vis[v]&&dis[u]+w<dis[v]){
dis[v]=dis[u]+w; //更新
pq.push(make_pair(-dis[v],v));
}
}
}
}
int query(int x){
int res=0;
for(int i=0;i<mn;i++){
if(dis[i]<=x)res+=(x-dis[i])/mn+1;
}
return res;
}
signed main(){
// freopen("school.in", "r", stdin);
// freopen("school.out", "w", stdout);
n=rd;l=rd;r=rd;
for(int i=1;i<=n;i++){
int x=rd;
if(x){//跳过a[i]=0
a[++m]=x;
mn=min(mn,x);
}
}
for(int i=0;i<mn;i++){
for(int j=1;j<=m;j++){
if(a[j]!=mn)add(i,(i+a[j])%mn,a[j]);
}
}
// cerr<<mn<<endl;
djstr(0);
// cerr<<"ok\n";
cout<<query(r)-query(l-1);
return 0;
}
/*
5 3 3
2 3 4 7 6
*/
例题 #3 [THUPC 2023 初赛] 背包¶
题目描述
本题中，你需要解决完全背包问题。
有 \(n\) 种物品，第 \(i\) 种物品单个体积为 \(v_i\)、价值为 \(c_i\)。
\(q\) 次询问，每次给出背包的容积 \(V\)，你需要选择若干个物品，每种物品可以选择任意多个（也可以不选），在选出物品的体积的和**恰好**为 \(V\) 的前提下最大化选出物品的价值的和。你需要给出这个最大的价值和，或报告不存在体积和恰好为 \(V\) 的方案。
为了体现你解决 NP-Hard 问题的能力，\(V\) 会远大于 \(v_i\)，详见数据范围部分。
输入格式
第一行两个整数 \(n,q\)，表示物品种数和询问次数。
接下来 \(n\) 行每行两个整数 \(v_i,c_i\) 描述一种物品。
接下来 \(q\) 行每行一个整数 \(V\) 描述一次询问中背包的体积。
输出格式
对于每组询问输出一行一个整数。若不存在体积和恰好为 \(V\) 的方案，输出 -1；否则输出最大的选出物品的价值和。
对于所有测试数据，\(1 \le n \le 50, 1 \le v_i \le 10^5, 1 \le c_i \le 10^6, 1 \le q \le 10^5, 10^{11} \le V \le 10^{12}\)。
题目来源¶
来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）初赛。
题解等资源可在 https://github.com/THUSAAC/THUPC2023-Pre 查看。
本题有助于我们完全了解同余最短路。
对于总容量很大的完全背包问题，我们通常会使用同余最短路。并且我们会发现，最后的最优方案一定是某个性价比最高的物品重复很多次，然后剩下一些物品在一个小范围内。
并且我们考虑同余最短路（就考虑例题 #1（前情回顾）的），我们发现最后答案的组成也是某个很小的 \(by+cz\)，再加上很大的 \(ax\) 组成的。
因此我们的 \(x\) 要选什么就很显然啦，就是性价比最高的那个。下面我们就令 \(x\) 为性价比最高的物品的编号
那么接下来怎么做呢？我们怎么样取确定一条边的边权，还有，怎么样统计答案？
这里我们先回到背包问题的基本做法上，dp。
定义 \(f_i\) 为选择物品的体积为i时的最大价值。那么我们就有：
\(f_i=\max(f_{i-kv_j}+kc_j)\)
但是我们不太可能取枚举 \(k\) 又要枚举 \(j\)，因此我们直接考虑从体积为 \(j\) 到体积为 \(i\) 的最优价值差。即我们写成以下形式：
\(f_i=\max(f_j+w(i-j))\)
我们发现，只要体积是 \(v_x\) 的整数倍，我们就使用一个 \(x\) 替代。于是有：
\(f_i=\max(f_j+\lfloor\frac{(i-j)}{v_x}\rfloor\times c_x+f_{(i-j)\bmod v_x})\)
然后呢？
如果放在同余最短路上，那么我们所有的下标都对 \(v_x\) 取模，那么 \(f\) 值会越滚越大，并且没有人知道它滚了几圈！
但是如果我们不知道它滚了几圈，我们怎么样确定最后我们需要多少个 \(x\) 才可以凑到询问的 \(V\) 呢？
因此我们需要改进以下我们的 dp。将 \(f\) 的定义修改为选体积为 \(i\)（在模 \(v_x\) 意义下）的物品，其与最优选法的最小差值。这里的最优选法自然就是只选 \(x\) 物品。当然这个差值有正有负，因为 \(x\) 可能选不满体积 \(i\)。
不过我们不管这些。只要我们求出了 \(f\)，那么答案就很简单了。对于询问 \(V\)，除去凑数的一大堆 \(x\)，剩下的就是 \(V\bmod v_x\)，那么差值就是 \(f_{V\bmod v_x}\)。加上只选 \(x\) 的最优选法的价值 \(\lfloor\frac{V}{v_x}\rfloor\times c_x\) 就是答案。
\(f_i=\max(f_{(i+v_j)\bmod v_x}+\lfloor\frac{i+v_j}{v_x}\rfloor\times c_x)\)
考虑跑最短路（当然这里应该是最长路）就相当于从一个状态加上一些权值变成下一个状态，那么按照上面的转移建图即可。
这里丢一个带 SLF 优化的代码。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pf first
#define ps second
#define cdbg(x) cerr<<#x<<" = "<<x<<'\n';
#define rd read()
inline int read(){
int x;
cin>>x;
return x;
}
const int N=2e6+5;
const int INF=1e18;
const int MOD=998244353;
/*
策略
同余最短路解决完全背包问题，这是一个典型的题目
但是本题除了要求恰好意外，还要要求价值最大。
先考虑贪心，发现对于最优解的很大一部分容量，都是在取性价比最高的物品。这是我们写同余最短路的一个很重要的限制：
我们的模数旧应该是取的次数异常多的数字
然后呢？我们每条路的长度应该是多少？
根据要求，应该是使得我们求出的f_i为k%mod=i中性价比最高的
但是注意这里的性价比和mod有关，因为如果我们取的越少，那么我们的mod就可以取得越多
*/
list<int> q;
int d[N];
bitset<N> vis;
struct edge{
int v,w;
};
vector<edge> e[N];
void add(int a,int b,int c){
// cerr<<a<<' '<<b<<' '<<c<<endl;
e[a].pb({b,c});
}
void spfa(){
memset(d,-0x3f3f,sizeof d);
d[0]=0;
q.push_back(0);
while(q.size()){
int x=q.front();
q.pop_front();
vis[x]=0;
for(auto v:e[x]){
if(d[v.v]<d[x]+v.w){//最长路
d[v.v]=d[x]+v.w;
if(!vis[v.v]){
if(d[v.v]>d[q.front()])
q.push_front(v.v);
else q.push_back(v.v);
vis[v.v]=1;
}
}
}
}
}
int mid=1,v[N],c[N];
void solve(){
int n=rd;
int q=rd;
for(int i=1;i<=n;i++){
v[i]=rd;
c[i]=rd;
if(v[mid]*c[i]>v[i]*c[mid])mid=i;
}
cdbg("OK");
for(int i=1;i<=n;i++){
if(i==mid)continue;
for(itn j=0;j<v[mid];j++){
add(j,(j+v[i])%v[mid],c[i]-(j+v[i])/v[mid]*c[mid]);
// add(j,(j+v[i])%v[mid],c[j]-((j+v[i])%v[mid]+v[j])/v[mid]*c[mid]);
}
}
spfa();
cdbg(v[mid]);
while(q--){
int V=rd;
int res=V/v[mid]*c[mid]+d[V%v[mid]];
if(res<0)res=-1;
cout<<res<<endl;
}
}
signed main(){
int T=1;
while(T--){
solve();
// if(T)puts("");
}
return 0;
}