题目描述

对于等式

$$\sum_{i=1}^{n}{a_{i} x_{i}}=B(B \in[l, r])$$

求有多少 $B$ 可以使该等式存在非负整数解

$1 \leq n \leq 12$

$0 \leq a_i \leq 5 \times 10^{5}$

$1 \leq l \leq r \leq 10^{12}$

简要做法

DP

很容易想到 完全背包，用 $f_{i}$ 表示 $B$ 的值能否为 $i$，那么转移方程为

$$ f_{j}=f_{j} \mid f_{j-a_{i}} $$

时间复杂度 $O(nr)$

洛谷 P5020 货币系统 O(nr) 
#include <memory.h>
#include <stdio.h>
#include <algorithm>

const int N = 1e2;
const int M = 25e3;

int n, m, ans;
int a[N + 5];
bool f[M + 5];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

int main()
{
    for (int T = read(); T--;)
    {
        ans = 0, m = 0;
        memset(f, false, sizeof f);
        f[0] = true;
        n = read();
        for (int i = 1; i <= n; i++)
            a[i] = read(), m = std::max(m, a[i]);
        std::sort(a + 1, a + 1 + n);
        for (int i = 1; i <= n; i++)
            if (!f[a[i]])
            {
                ans++;
                for (int j = a[i]; j <= m; j++)
                    f[j] |= f[j - a[i]];
            }
        printf("%d\n", ans);
    }
    return 0;
}

最短路

任意取一个 $a_i$，设为 $w$

如果存在 $\sum_{i=1}^{n}{a_{i} x_{i}}=t$

必然存在 $\sum_{i=1}^{n}{a_{i} x_{i}}=t + k \times w$

把 $[0,w-1]$ 中的每个正整数视为一个点，每个点有 $n-1$ 条出边，$i$ 号点的第 $j$ 条出边指向 $(i+a_j)\bmod w$ 号点，边权为 $a_j$

那么 $dis_i$ 表示能够到达的最低的 $\bmod \ w = i$ 的数

然后从 $0$ 号点出发跑单源最短路即可，因为建边方式比较特殊，所以 SPFA 不会被卡，跑起来挺快的

洛谷 P3403 跳楼机 
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <queue>

typedef long long ll;

const ll N = 5e5 + 5;
const ll M = 6e6 + 5;
const ll INF = (1LL << 63) - 1;

ll n, h, w;
ll a[N], dis[N];
ll head[N], num_edge;
bool inQ[N];

struct Node
{
    ll next, to, dis;
} edge[M];

void add_edge(ll u, ll v, ll dis) { edge[++num_edge] = Node{head[u], v, dis}, head[u] = num_edge; }

ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void SPFA(ll s)
{
    memset(dis, 0x3f, sizeof dis);
    std::queue<ll> Q;
    dis[s] = 0, Q.push(s), inQ[s] = true;
    while (!Q.empty())
    {
        ll u = Q.front();
        Q.pop(), inQ[u] = false;
        for (ll i = head[u]; i; i = edge[i].next)
        {
            ll v = edge[i].to, dist = edge[i].dis;
            if (dis[v] > dis[u] + dist)
            {
                dis[v] = dis[u] + dist;
                if (!inQ[v])
                    Q.push(v), inQ[v] = true;
            }
        }
    }
}

ll query(ll x)
{
    ll res = 0;
    for (ll i = 0; i < w; i++)
        if (dis[i] <= x)
            res += (x - dis[i]) / w + 1;
    return res;
}

signed main()
{
    n = 3, h = read();
    w = INF;
    for (ll i = 1; i <= n; i++)
        a[i] = read(), w = std::min(w, a[i]);
    for (ll i = 0; i < w; i++)
        for (ll j = 1; j <= n; j++)
            if (a[j] != w)
                add_edge(i, (i + a[j]) % w, a[j]);
    SPFA(0);
    printf("%lld", query(h - 1));
    return 0;
}
洛谷 P2371 [国家集训队]墨墨的等式 
#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <queue>

typedef long long ll;

const ll N = 5e5 + 5;
const ll M = 6e6 + 5;
const ll INF = (1LL << 63) - 1;

ll n, l, r, w;
ll a[N], dis[N];
ll head[N], num_edge;
bool inQ[N];

struct Node
{
    ll next, to, dis;
} edge[M];

void add_edge(ll u, ll v, ll dis) { edge[++num_edge] = Node{head[u], v, dis}, head[u] = num_edge; }

ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while ('0' > ch or ch > '9')
        f = ch == '-' ? -1 : 1, ch = getchar();
    while ('0' <= ch and ch <= '9')
        x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}

void SPFA(ll s)
{
    memset(dis, 0x3f, sizeof dis);
    std::queue<ll> Q;
    dis[s] = 0, Q.push(s), inQ[s] = true;
    while (!Q.empty())
    {
        ll u = Q.front();
        Q.pop(), inQ[u] = false;
        for (ll i = head[u]; i; i = edge[i].next)
        {
            ll v = edge[i].to, dist = edge[i].dis;
            if (dis[v] > dis[u] + dist)
            {
                dis[v] = dis[u] + dist;
                if (!inQ[v])
                    Q.push(v), inQ[v] = true;
            }
        }
    }
}

ll query(ll x)
{
    ll res = 0;
    for (ll i = 0; i < w; i++)
        if (dis[i] <= x)
            res += (x - dis[i]) / w + 1;
    return res;
}

signed main()
{
    n = read(), l = read(), r = read();
    w = INF;
    for (ll i = 1; i <= n; i++)
        a[i] = read(), w = std::min(w, a[i]);
    for (ll i = 0; i < w; i++)
        for (ll j = 1; j <= n; j++)
            if (a[j] != w)
                add_edge(i, (i + a[j]) % w, a[j]);
    SPFA(0);
    printf("%lld", query(r) - query(l - 1));
    return 0;
}