.png)
关于同余最短路, 我这个蒟蒻刚刚遇到, 大概看了一下, 感觉挺有意思, 故写了这篇博客.
(暂时未完工)
注意
因作者不喜欢太过于正式的表述, 故会使用一些不正规的语言, 介意者请注意.
仅有简单例题, 已经熟练掌握此技巧者可以离开了, 我这个蒟蒻刚刚学会......
不多说了, 我们开始吧.
思想
想差分约束一样, 当我们发现可以通过同余构造类似带权有向边的状态时
我们就可以将一些问题转化为最短路问题, 使用一些效率强大的算法解决问题
具体很难直接说, 我们通过例题看
例题:
题意の简述
给定 x, y, z, h, 对于 k\in[1,h], 询问有多少个 k 可以满足: ax+by+cz=k (OI wiki 的题意简化)
数据范围: 0\le a,b,c , 1\le x,y,z \le 10^5 , h \le 2^{63}-1
看着想不想数学题, 我看着也像, 但是如果我们深入思考会发现难以求解
我们若想求解, 我们需要固定两个变量 (反正我觉得需要)
However, 我们似乎没有办法用数学做到
我有一计
来自神秘先辈的记忆碎片告诉我们, 对于这个问题, 我们可以考虑同余最短路(同余最短路特征后边再说)
我们发现刚才说的确实没有什么问题, 神秘先辈告诉我们转换称图论问题
瞪眼一看, 我们发现一个可行的 k 到另一个可行的 k 长得就像一个点通过有一个权值的边到另一个点
想不想我们熟悉的
dis[v]=dis[u]+w ?
我们可以类比整出来
K_v=K_u+p (p\in \left \{a,b,c \right \} )
搞笑的是, 我们 h 的范围太大了, 没有办法让我们这么去搞
我们现在只需要加上我们最重要的一步
取模
通过找 x,y,z 中一个比较小的值(若差不多大就无所谓啦), 通过对这个值进行取模, 最后将取模过后的数最后一起计算, 我们就可以正确解决问题了
到这个例子, 我们可以做如下操作
我们选择 x 做为上边说的数字, 我们将\mod x 的各个 k 放到一起, 最后再统计答案的时侯直接一并计算
具体如下:
我们设 f(i) 代表我们使用随便多少个 y,z 所拼出来的 k 之中\mod x=i 的最小的一个 k.
why如此设计?
我们固定了 y,z, 从而可以算方案数, 我们可以将这个 f(i) 理解为使用 x 的"底线", 在对于每一个 i 计算方案的时侯, 我们就可以通过 \left \lfloor \frac{h-f(i)}{x} \right \rfloor + 1 来表示当前 i 的总方案数.
这样我们就可以求解了
考虑一下怎么求出 f(i)?
我们上边不是正好发现了 k 类似最短路的性质吗?
加上取模我们不难列出如下式子
f(i)+y \ge f((i+y)\mod x)
f(i)+z \ge f((i+z)\mod x)
那我们将 i 与 (i+y)\mod x 作为两个点 连接上一条权值为 y 的单向边
那同理将 i 与 (i+z)\mod x 作为两个点 连接上一条权值为 z 的单向边
跑我们的 Dijkstra/Spfa, 我们就得到了我们想要的 f(i).
我们然后就可以从 0 到 h-1 按上边的方法求就可以了
代码
粘一下, 个人码风或许有些奇怪
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=3e6+316;
struct Node{
int nxt, to, w;
}node[MN];
int head[MN], tottt;
inline void insert(int u, int v, int w){
node[++tottt].to=v;
node[tottt].w=w;
node[tottt].nxt=head[u];
head[u]=tottt;
}
int dis[MN], vis[MN];
priority_queue <pair<int,int>> q;
void Dijkstra(int s){
for(int i=0; i<MN; ++i) dis[i]=0x3f3f3f3f3f3f3f3f;
memset(vis,0,sizeof(vis));
dis[s]=0; q.push({0,s});
while(!q.empty()){
int u=q.top().second; q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=node[i].nxt){
int v=node[i].to, w=node[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({-dis[v],v});
}
}
}return;
}
int h, x, y, z, ans=0;
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin>>h>>x>>y>>z; --h;
for(int i=0; i<x; ++i){
insert(i,(i+y)%x,y);
insert(i,(i+z)%x,z);
}
Dijkstra(0);
for(int i=0; i<x; i++)
if(h>=dis[i]) ans+=(h-dis[i])/x+1;
cout<<ans<<'\n';
return 0;
}
例题2.0
题意の简述
{\textstyle \sum_{i=1}^{n}a_ix_i=b} 我们给定 a_i , 求有多少 b\in [l,r] 可以使这个等式存在非负整数解
我们已经知道了像上一道题那样的题目可以使用同余最短路, 这个题无非就是多了一些 x,y,z, 道理都一样, 我们找一个最小的做模数, 然后向前边这么做就行了, 对与 [l,r] 我们像处理前缀和一样将 ans(r)-ans(l-1) 就行了.
放一下代码, 注意这个题有个 a_i 为 0 的 hack.
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MN=5e6+316;
struct Node{
int nxt, to, w;
}node[MN];
int head[MN], tottt;
inline void insert(int u, int v, int w){
node[++tottt].to=v;
node[tottt].nxt=head[u];
node[tottt].w=w;
head[u]=tottt;
}
int dis[MN], vis[MN];
priority_queue <pair<int,int>> q;
void Dijkstra(int s){
for(int i=0; i<MN; ++i) dis[i]=LLONG_MAX;
memset(vis,0,sizeof(vis));
q.push({0,s}); dis[s]=0;
while(!q.empty()){
int u=q.top().second; q.pop();
if(vis[u]) continue;
vis[u]=true;
for(int i=head[u];i;i=node[i].nxt){
int v=node[i].to, w=node[i].w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({-dis[v],v});
}
}
}
}
int n, l, r, a[MN], minn=0x3f3f3f3f3f3f3f3f, mem=0;
int query(int x){
int res=0;
for(int i=0; i<minn; ++i){
if(x>=dis[i]) res+=((x-dis[i])/minn)+1;
}
return res;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>l>>r;
for(int i=1; i<=n; ++i){
cin>>a[i]; if(!a[i]) continue;
if(a[i]<minn){
minn=a[i];
mem=i;
}
}
for(int i=0; i<minn; ++i){
for(int j=1; j<=n; ++j){
insert(i,(i+a[j])%minn,a[j]);
}
}
Dijkstra(0);
cout<<query(r)-query(l-1)<<'\n';
return 0;
}
题就先这样, 给一下特征和练习
特征&练习
一般有以下特征
- 大范围目标值
- 固定整数集合
- 线性组合形式(拼凑整数的存在性,计数或最小不可表示问题)
我个人觉得就是这个样子吧......
再给一点题