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

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]$的最小值也就被转化成了最短路问题。
那么算法就得出来了：

1. 首先求一下$a_{min}$的最小值保存下来。
2. 跑最短路，预处理出D数组。
3. 枚举所有的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$范围内的数的问题其实是很经典的图论问题，像这种建图困难，但是最短路很好跑的题目便可以称为是建图题了。