同余最短路总结

· · 题解

20190928 重新修了一下此篇博客,修改了码风

同余最短路，并不是用同余来跑最短路，而是通过同余来构造某些状态，从而达到优化时间空间复杂度的目的。往往这些状态就是最短路中的点，可以类比差分约束跑最短路(f[i]+w<=f[j]构造最短路不等式(如 小k的农场))

luogu P3403跳楼机

题意：求ax+by+cz=K,\{K∈[1,h];x,y,z∈N\}，有多少K满足条件
类比(NOIP~2018~T2)(也可以用同余最短路来跑,然而当年手推exgcd),区别就在货币系统限制了货币的上限a[i]<=25000,所以可以用背包来跑。但是这道题的最大上限达到了1e18,所以就要用到同余最短路来优化。

先考虑简单情况,假设只有两个数x\&y（即z=0）,可以考虑用ax来凑出所有ax\%b==[0,b-1]中到每个状态点[0,b-1]的最小x所用值。下面对最小有解释。

设dis[i]表示到i号状态点时,所需花费的最小a*x,也就是要达到状态ax\%b==i使用a跳楼机的最小次数x。

这里有两个地方需要理解：

建边方式
adde(u = i, v = ( i + a ) % b, w = a);

统计答案
for ( i = 0; i < y; ++i) if (h >= dis[i]) ans += (h - dis[i]) / b + 1;

统计答案时直接算b的系数y有多少种可能就行了,这样相当于固定了一个同余系b，对于每一个状态i,加上b*y一定不会重复统计楼层。

然后考虑如题情况,三元不定方程ax+by+cz=N,设c=min(a,b,c),为了最大节省空间时间,我们取模数最小值,（即使得同余系最小）,设最小数同余系参数为c，状态点数为0 ~ c-1。
建边方式为 adde(i, (i+a)%c, a) 和 adde(i, (i + b) % c, b)
统计答案仍为对于每一个状态点i,计算c的系数z的取值个数。
即if ( h >= dis[i] ) ans += (h - dis[i]) / c + 1;

拓展：如果要单独讨论x能否被取到，x能被取到的充要条件 d[x\%a_i] <= x，这里的a_i是之前钦定的最小模数。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#define rr register int
using namespace std; 
typedef long long ll;
inline ll read(){
    char i = getchar();
    ll dp = 1, res = 0;
    while (i < '0' || i > '9') {
        if (i == '-') dp = -1;
        i = getchar();
    }
    while (i >= '0' && i <= '9') {
        res = res * 10 + i - '0';
        i = getchar();
    }
    return res * dp;
}
const int N = 1e5 + 50;
struct zk{
    int v, next;
    ll w;
}ed[N << 2];
int head[N], cnt=0, vis[N];
ll dis[N];
inline void adde(int u, int v, ll w){
    ed[++cnt].v = v;
    ed[cnt].w = w;
    ed[cnt].next = head[u];
    head[u] = cnt;
}
ll h, x, y, z;
queue<int> q;
void SPFA(){ //SPFA 板子 
    dis[1] = 1;
    vis[1] = 1;
    q.push(1);
    while (!q.empty()) {
        int u = q.front();
        vis[u] = 0;
        q.pop();
        for (rr i = head[u]; ~ i; i = ed[i].next) {
            int v = ed[i].v, w = ed[i].w;
            if (dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main(){
    memset(head, -1, sizeof(head));
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    h = read(), x = read(), y = read(), z=read();
    for (rr i = 0; i < z;++i) {
        adde(i, (i + x)% z, x);
        adde(i, (i + y)% z, y);//表示从i到下一个点(i+y)%z 
    }
    SPFA();
    ll ans = 0;
    for(rr i = 0; i < z; ++i) {
        if(h >= dis[i]) 
            ans += (h - dis[i]) / z + 1;
    }
    printf("%lld\n",ans);
}