1.同余最短路

省选模拟赛 T3 一小部分用到了同余最短路，发现这简单东西自己从来没学过，补一下。

\(n\) 个正整数，分别为 \(A_1,A_2,\cdots,A_n\)，求 \([0,V]\) 中有多少个数可以被表示为 \(\sum\limits_{i=1}^{n} A_ix_i,x_i\in \mathbb{N}\)。

可以完全背包，但复杂度 \(O(nV)\)，当 \(V\) 很大的时候复杂度直接上天，我们想要找到一种与 \(V\) 无关的算法。

发现如果 \(x\) 可达，那么 \(x+kA_1,k\in \mathbb{N}\) 都可达。也就是对于每个模 \(A_1\) 的同余类 \([x]\)，记其中可达的最小值为 \(d_x\)，则这个同余类中所有大于等于 \(d_x\) 的数都可达。

假设现在我们知道 \(d_x\)，我们加入一个数 \(v\)，相当于有对 \(y=(x+v)\bmod A_1\) 有一个转移 \(d_y=min(d_y,d_x+v)\)，类似最短路的形式。所以我们对于 \(i\in [2,n],j\in [0,A_1)\) 都建一条边 \(j\to (j+A_i)\bmod A_1\)，边权为 \(A_i\)，再在这个图上跑最短路，得到的答案即为每个同余类中可达的最小的数。

这样点数为 \(A_1\)，边数为 \(nA_1\)，使用 dij 的话时间复杂度 \(O(nA_1+n\log (nA_1))\)。

但是其实最短路是不必要的，对于一个数 \(v\)，在模 \(m\) 时像上面那样建边，会形成 \(\gcd(v,m)\) 个子环，更新只会在同一个子环中进行，在没有负环的时候更新肯定不会转满一整圈，所以只需要在这个环里转两圈就可以把所有可能的更新都进行完。

这样枚举 \(n-1\) 个数字，时间复杂度 \(O(nA_1)\)。

可以选择最小的数作为 \(A_1\) 来减小常数。

P3403 跳楼机 板子。

    memset(dis,63,sizeof(dis));
    for(int i=0;i<x;++i)
        add(i,(i+y)%x,y),add(i,(i+z)%x,z);
    q.push({1,1%x});dis[1%x]=1;
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x]) continue;vis[x]=true;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=to[i];
            if(dis[y]>dis[x]+val[i])
                dis[y]=dis[x]+val[i],q.push({dis[y],y});
        }
    }
    for(int i=0;i<x;++i)
        if(dis[i]<=h) ans+=(h-dis[i])/x+1;

    memset(dis,63,sizeof(dis));dis[1%x]=1;
    for(int i=0,lim=__gcd(y,x);i<lim;++i)
    {
        for(int cnt=0,p=i;cnt<2;cnt+=p==i)
        {
            int q=(p+y)%x;
            dis[q]=min(dis[q],dis[p]+y);p=q;
        }
    }
    for(int i=0,lim=__gcd(z,x);i<lim;++i)
    {
        for(int cnt=0,p=i;cnt<2;cnt+=p==i)
        {
            int q=(p+z)%x;
            dis[q]=min(dis[q],dis[p]+z);p=q;
        }
    }
    for(int i=0;i<x;++i)
        if(dis[i]<=h) ans+=(h-dis[i])/x+1;

P8060 [POI2003] Sums 也是板子。

P2371 [国家集训队] 墨墨的等式 仍是板子。

P2662 牛场围栏 还是板子。

答案是 \(\max\{(\lfloor\dfrac{d_i}{A_1}\rfloor-1)A_1+i,0\}\)。

P9140 [THUPC 2023 初赛] 背包

贪心加同余最短路。特殊的数据范围保证了 \(V\) 的下界，所以贪心的以性价比最高的为基准物品，跑同余最短路。转移时 \(d_y=\max(d_y,d_x+c_i-\lfloor\dfrac{x+v_i}{v_1}\rfloor c_1)\)。答案是 \(d_{V\bmod v_1}+\lfloor\dfrac{V}{v_1}\rfloor c_1\)。

[ABC077D] Small Multiple

不太常规，记 \(d_x\) 为模 \(k\) 的同余类 \([x]\) 中最小的数位累加和，对于 \(i\in [0,k)\) 分别建 \((i,(i+1)\bmod k,1)\) 和 \((i,(i*10)\bmod k,0)\) 的边，分别表示最后一位加一和扩大十倍，这样可以构造出所有数字。初始使 \(d_1=1\)，答案为 \(d_0\)。

[ARC112F] Die Siedler

人类智慧转化一下。推个式子，然后根号分治。根号分治里一半是简单同余最短路。

我就是为了这碗醋才包的这顿饺子。但是我懒得写这题题解了。

算法学习笔记(93): 同余最短路

同余最短路的转圈技巧