同余最短路

· · 题解

概念

同余最短路是一种优化最短路建图的方法

通常是解决给定 m 个整数，求这 m 个整数能拼凑出多少的其他整数(这 m 个整数可以重复取)或给定 m 个整数，求这 m 个整数不能拼凑出的最小（最大）的整数。

栗题

P2371 [国家集训队]墨墨的等式

题目大意：

对于 \sum_{i = 1}^na_ix_i = b​ ，给定 n​ ，a_{1 \cdots n}​ ，l​，r​ ，求有多少 b \in[l,r]​ 可以使得等式存在非负整数解。

solution

把题目稍微变一下形

求有多少组 x_i​​ ，使得 a_1 \times x_1 + a_2 \times x_2 \cdots a_n \times x_n = b​​ 成立

发现这个题和货币系统那个题很像，考虑完全背包做法，但是这个题的 l, r 很大，所以就有了同余最短路。

好像题解解释的都不是很清楚 ？？这用分组的思想感觉解释好像能解释的更清楚点 = =

对于这个题，我们可以先求出 [1, l - 1] 有多少 b 满足条件，再求出 [1, r] 有多少 b 满足条件，作差就好了。

转换一下，与其考虑 b 是否满足条件，不如考虑 b 是否能被凑出来。

好，现在我们的目标就是统计 [1,x] 内有多少个数能被凑出来。

考虑这么一件事：找出 a_i 中最小的记为 Min ，令 p \in[1, Min)；

我们所有的数按照对 Min 取模，按照余数分为 Min 类。

如果 p + k*Min​ 能够被凑出来，那么 p + (k + N^{+}) \times Min​ 也一定能被凑出来，也就是从这之后，这一类都能被凑出来了，令 tmp = p + k_{min} \times Min​ ，也就是这一类最早能被凑出来的数。如果 tmp \leq x​，那么这个区间关于这一类能凑出来的数的个数就是 \frac{x - tmp}{Min} + 1​ ，求所有类就是对每一类数做相同操作加和就好了。

现在就只剩怎么求每一类被第一次凑出来的数是多少。

把它放在图里，让 p​ 向 (p +a_i) \bmod Min​ 连一条权值为 a_i​ 有向边，也就是说凑出 p + a_i​ 的代价为 a_i​ ，从 0​ 点到 [0, Min)​ 的最短路长度就是每一类第一次被凑出来的数是多少。

然后就完成啦。

code

/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long
#define rg register
using namespace std;
const int N = 5e5 + 5;
const int M = 6e6 + 5;
const int INF = 0x3f3f3f3f3f3f;
int read(){
    int x = 0,f = 1; char c = getchar();
    while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
    return x*f;
}
int n, l, r, a[N], m, Min = INF, dis[N], vis[N];
struct edge {int v, nxt, w;}e[M]; 
int head[N], E;
void add_edge(int u, int v, int w) {
   e[++E] = (edge) {v, head[u], w};
   head[u] = E;
}
queue<int> q;
void SPFA(int s) {
   memset(dis, INF, sizeof dis); 
   dis[s] = 0, q.push(s);
   while(!q.empty()) {
      int u = q.front(); q.pop(); vis[u] = 0;
          for (rg int i = head[u]; i; i = e[i].nxt){
            int v = e[i].v, w = e[i].w;
            if (dis[v] > dis[u] + e[i].w){  
               dis[v] = dis[u] + e[i].w;
               if (!vis[v]) q.push(v), vis[v] = 1;
            }
        }
   }
}
int query(int x) {
    int res = 0;
    for (rg int i = 0; i < Min; i++) 
       if (dis[i] <= x)
          res += (x - dis[i]) / Min + 1;
    return res;
}
signed main(){
   n = read(), l = read(), r = read();
   for (rg int i = 1, x; i <= n; i++) {
       x = read();
       if (x) a[++m] = x, Min = min(x, Min);//0 边没有贡献 
   }
   n = m;
   for (rg int i = 0; i < Min; i++) 
      for (rg int j = 1; j <= n; j++)
          if (a[j] != Min) add_edge(i, (i + a[j]) % Min, a[j]);
   SPFA(0);
   printf("%lld", query(r) - query(l - 1));
   puts("");
   return 0;
}

这道题的弱化版 P3403 跳楼机

注意这道题是从一楼开始，想想与上面板子比较哪里变了 = =

finish