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

Link
题意大概就是求 $B_l,B_r$ 范围内 $B$ 的个数使等式

$\sum_{i = 1}^N a_Nx_N = B$

存在非负整数解。其实转化一下题意也就是

在N种物品中任意选择，物品有一个价值，使得最后的总价值处于给定区间内。

这很显然是一个完全背包，而且是类似于一种模板题，但是这道题的数据范围是 $B \leq 10^{12}$ ，因此这么做显然是不行的，但是我们可以从完全背包的视角出发思考题目。
我们取出最小的 $a$ 为 $a_{min}$ ,并且假设我们现在知道了一种方案，物体的总重为 $D[i]$ ，并且满足 $K ~mod~ a_{min} = i$ ，在这两种条件下 $D[i]$ 为最小值。
那么显然，对于任意一个同样满足上述两个条件的总重X， $X \leq D[i]$ ，并且因为 $X ~mod~ a_{min} = D[i] ~mod~ a_{min}$ ，所以可以知道 $X$ 方案可以由 $D[i]$ 方案加上若干个 $a_{min}$ 得到。
现在我们考虑加入一个物体 $Now$ ，那么有

$D[(i + Now) ~mod~ a_{min}]$

可以从 $d[i] + Now$ 而来。于是可以考虑从i向 $(i + Now) ~mod~ a_{min}$ 连一条比边权为 $Now$ 的边，而求 $D[i]$ 的最小值也就被转化成了最短路问题。
那么算法就得出来了：

首先求一下 $a_{min}$ 的最小值保存下来。

跑最短路，预处理出D数组。

枚举所有的D，计算mod T = i的数在区间 $B_l,B_r$ 中有多少个。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std ;

typedef long long LL ;
const int MAXN = 15 ;
const int MAXM = 500010 ;
LL Inf = (LL)1 << 60 ;

LL N, L, R, a[MAXN], H[MAXN], Tot, D[MAXM] ;
struct Edge {int F, T, L, Next ;} E[MAXN] ;
queue<int> Q ; bool F[MAXM] ; LL K, Ans ;   

inline void Add(int F, int T, int L) {
    E[++ Tot].F = F ; E[Tot].T = T ; E[Tot].L = L ;
    E[Tot].Next = H[F] ; H[F] = Tot ;
}

inline void Spfa(int S) {
    memset(F, 0, sizeof(F)) ;
    for (int i = 1 ; i < K ; i ++) D[i] = Inf ;
    D[S] = 0 ; F[S] = 1 ; Q.push(S) ;
    while (! Q.empty()) {
        int Now = Q.front() ; Q.pop() ; F[Now] = 0 ;
        for (int i = 1 ; i <= N ; i ++) {
            int T = (Now + a[i]) % K ;
            if (D[T] > D[Now] + a[i]) {
                D[T] = D[Now] + a[i] ;
                if (! F[T]) Q.push(T), F[T] = 1 ;
            }
        }
    }
}

inline LL Read() {
    LL X = 0, F = 1 ; char ch = getchar() ;
    while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
    while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
    return X * F ;
}

int main() {
    N = Read(), L = Read(), R = Read() ;
    for (int i = 1 ; i <= N ; i ++) a[i] = Read() ;
    sort (a + 1, a + N + 1) ; K = a[1] ; //储存最小的a。
    Spfa(0) ;
    for (int i = 0 ; i < K ; i ++)
        if (D[i] != Inf) D[i] = (D[i] - i) / K ;
    for (int i = 0 ; i < K ; i ++)
        if (D[i] != Inf) {
            int K1 = (L - i - 1) / K - D[i] + 1 ;
            int K2 = (R - i) / K - D[i] + 1 ;
            Ans = Ans - max(K1, 0) + max(K2, 0) ;
        }
    printf("%lld", Ans) ; return 0 ;
}

这种在求解用 $\{a_i\}$ 能组成多少个在 $B_l, B_r$ 范围内的数的问题其实是很经典的图论问题，像这种建图困难，但是最短路很好跑的题目便可以称为是建图题了。