同余最短路

· · 个人记录

同余最短路

引入

先介绍一下大家熟知的差分约束问题，通过建图将线性规划问题转化为图论问题。

给定多个形如a_i-a_j\ge c_{ij}的不定式，找出一种可行解。

这种问题有一种很巧妙的构造方法，就是将这类问题抽象成一个图论问题来解决。

具体来说，就是将不等式移项，变为a_i\ge a_j+c_{ij}，发现很像最短（长）路中的式子。

在每条边都松弛完成之后，在最短路中每条边都满足d_y\le d_x+z（不存在负环），反之可以继续松弛。同理，在最长路中每条边都满足d_y\ge d_x+z（不存在正环）。

如此，发现和原来的不等式很像，于是连接j到i，边权为c_{ij}的边，跑一边最长路，就得到了原问题的一种可行解。

这个东西叫做三角不等式，将一类线性规划问题通过三角不等式转换为图论问题解决，成功在多项式时间复杂度之内解决了这个难题。

我们发现通过建图将数学问题转化为图论问题的思路很好，尝试推广一下。

例题1

题目传送门：P3403 跳楼机。

题意简述：给定一栋大楼，从一楼开始，每次可以向上走x,y,z层楼，问可以到达的楼层数。

数据范围：楼高1 \le h\le 2^{63}-1，每次移动的距离1\le x,y,z\le10^5。

提示：这是道图论题，由博客标题可知。

Solution

我们发现h很大，设最后到达的楼层数为D，有D=k_xx+k_yy+k_zz且满足k_x,k_y,k_z\in \text{N}。

然后你发现你只能固定k_x,k_y算出方案数，但h太大了，数论做法卒。

我们站在先人的肩膀上，考虑建图转化为图论问题。

我们发现每次执行一次操作，都是D_1=D_2+edge,edge\in{x,y,z}。这不是最短路问题吗？

在最短路松弛结束后，每个点都至少有一个入边满足d_y=d_x+z，于是可以建图最短路，找到所有点。

但是有一个新的问题，就是h的范围太大，最短路的时空复杂度都承担不下。

于是，我们考虑一个神奇的运算，取模！

发现我们只需将\text{mod }x后的值保存下来，在统计答案时在统计\text{mod } x同余的楼层一起计算即可。

这种将余数相同的数一起考虑，再建图转化为图论问题的思想被称为同余最短路！

具体来说，我们记f(i)为只通过若干加y和加z最后到达的楼层中\text{mod }x=i的最小楼层。

P.S记最小楼层是为了方便求出方案数。

写出状态转移方程式：

f((i+y)\%x)=f(i)+y\\f((i+z)\%x)=f(i)+z

将i,(i+y)\%x,(i+z)\%x视为点跑最短路即可，初始状态f(1)=1。

这样点和边的规模都变为和x,y,z有关，设x,y,z的值域为n，所以时间复杂度为O(nlogn)。

让我们再想想方案数怎么统计。

显然，对于每个f(i)我们最后只需考虑填x的方案数。

所以ans=\sum_{i=0}^x(\left \lfloor \frac{h-f(i)}{x} \right \rfloor +1)，O(n)计算即可。

代码如下：

SPFA已经死了无数次了，虽然这题不卡但还是用dijkstra吧。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+10,M=2e5+10;

int head[N],ver[M],edge[M],nxt[M],tot=1;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}

ll f[N],ans,h,X,Y,Z;
bool v[N];
priority_queue<pair<ll,int>>q;
void dijkstra(){
    memset(f,0x3f,sizeof(f));
    f[1]=1;q.push({1,1});
    while(q.size()){
        int x=q.top().second;q.pop();
        if(v[x])continue;
        v[x]=1;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(f[y]>f[x]+edge[i]){
                f[y]=f[x]+edge[i];
                q.push({-f[y],y});
            }
        }
    }
}

int main(){
    scanf("%lld%lld%lld%lld",&h,&X,&Y,&Z);
    if(X==1||Y==1||Z==1)printf("%lld\n",h),exit(0);
    for(int i=0;i<X;i++){
        add(i,(i+Y)%X,Y);
        add(i,(i+Z)%X,Z);
    }
    dijkstra();
    for(int i=0;i<X;i++)
        if(f[i]<=h)ans+=(h-f[i])/X+1;
    printf("%lld\n",ans);
    return 0;
}

例题2

题目传送门：[ABC077D] Small Multiple

题意简述：给定一个整数K，求一个K的倍数S，使得S在十进制下的数位和最小，输出最小数位和。

数据范围：2\le K \le 10^5。

Solution

这题有非常好的性质，对于每个S，每次\times 10对答案没有贡献；每次+1，答案+1。

于是这样就可做了，将每个S看作一个点，建图跑最短路，判断是否是K的倍数。

但是S可以很大，于是我们可以像上题一样，用取模压缩状态。

直接保存S\%K的值即可，还挺直接的。

边权只有0和1，01bfs也可做。

代码如下：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=1e5+10,M=2e5+10;

int head[N],ver[M],edge[M],nxt[M],tot=1;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}

ll f[N],n;
bool v[N];
priority_queue<pair<ll,int>>q;
void dijkstra(){
    memset(f,0x3f,sizeof(f));
    f[1]=1;q.push({1,1});
    while(q.size()){
        int x=q.top().second;q.pop();
        if(v[x])continue;
        v[x]=1;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(f[y]>f[x]+edge[i]){
                f[y]=f[x]+edge[i];
                q.push({-f[y],y});
            }
        }
    }
}

int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        add(i,(i+1)%n,1),add(i,(i*10)%n,0);
    dijkstra();
    printf("%lld\n",f[0]);
    return 0;
}

做过的最水紫题之一。

例题3

题目传送门：P2371 [国家集训队] 墨墨的等式

题意简述：求出[l,r]内有多少个K满足\sum_{i=1}^na_ix_i=K。

数据范围：$n \le 12，0 \le a_i \le 5\times 10^5，1 \le l \le r \le 10^{12}。

Solution

好熟悉，定睛一看，不是加强版的跳楼机吗？

差分一下，变为求[0,l-1]和[0,r]的贡献。做法如出一辙。

又水一道紫题。

代码如下：

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=5e5+10,M=6e6+10;

int head[N],ver[M],edge[M],nxt[M],tot=1;
void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
}

ll f[N],ans,n,l,r,a[N],m;
bool v[N];
priority_queue<pair<ll,int>>q;
void dijkstra(){
    memset(f,0x3f,sizeof(f));
    f[0]=0;q.push({0,0});
    while(q.size()){
        int x=q.top().second;q.pop();
        if(v[x])continue;
        v[x]=1;
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i];
            if(f[y]>f[x]+edge[i]){
                f[y]=f[x]+edge[i];
                q.push({-f[y],y});
            }
        }
    }
}

ll solve(ll x){
    ll ans=0;
    for(int i=0;i<a[1];i++)
        if(f[i]<=x)ans+=(x-f[i])/a[1]+1;
    return ans;
}

int main(){
    scanf("%lld%lld%lld",&n,&l,&r);
    for(int i=1,x;i<=n;i++){
        scanf("%d",&x);
        if(x)a[++m]=x;
    }
    for(int i=0;i<a[1];i++)
        for(int j=2;j<=m;j++)
            if(a[j]!=a[1])add(i,(i+a[j])%a[1],a[j]);
    dijkstra();
    printf("%lld\n",solve(r)-solve(l-1));
    return 0;
}

总结

学会同余最短路又可以水一堆题。

思路大概是：数论做法\Rightarrow建图等价转换\Rightarrow发现在\%K下等价，缩小数据范围。

注意模数的选取，不然会出问题。