【题解】墨墨的等式 剩余系最短路 BZOJ – 2118

https://www.mina.moe/BZPRO/JudgeOnline/2118.html

题目换句话说就是有 $n$个物品，每个物品有一个重量，每个物品可以选择无限次（完全背包），求最终总重量在 $[Bmin, Bmax]$中出现了多少次

嗯，首先我们设我们打算让所有取出的物品总重为 $w$

设第一个取的物品重量为 $t$，取了 $k$次

设除了第一个取的物品以外取的物品总重为 $v$

则有 $w = tk + v$

也就是说 $w \mod t = v \mod t$是 $w$能被取到的必要条件

因此我们对于所有的 $i(i \in [0, t – 1])$，计算使得 $v \mod t = i$的这个 $v$的最小值

（最小是因为大的能取到的位置小的都能取到）

然后对于每个 $i$都求出最小的 $v$后只需要判断 $tk + v \in [Bmin, Bmax]$这个不等式的 $k$有多少个解就可以了

复杂度为 $O(nt log _ 2 n)$（迪杰斯特拉，Spfa 我就不想说了）

由此可见复杂度与 $t$有关，$t$取最小的数即可。

代码：

#include <bits/stdc++.h>

#define NS (15)
#define NNS (500005)
#define MS (6000005)

using namespace std;

typedef long long LL;
typedef pair<LL, int> PLI;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, A[NS];

LL L, R;

struct Graph
{
    int head[NNS], nxt[MS], to[MS], w[MS], sz;
    Graph() {memset(head, -1, sizeof(head)), sz = 0;}
    void push(int a, int b, int c)
    {
        nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g;

priority_queue<PLI, vector<PLI>, greater<PLI> > pq;

LL dis[NNS];

bool book[NNS];

void Dij()
{
    fill(dis + 1, dis + A[0], LLONG_MAX), pq.push(PLI(0, 0));
    while (!pq.empty())
    {
        int a = pq.top().second; pq.pop();
        if (book[a]) continue;
        book[a] = 1;
        for (int i = g.head[a]; ~i; i = g.nxt[i])
            if (dis[a] + g.w[i] < dis[g[i]])
                dis[g[i]] = dis[a] + g.w[i], pq.push(PLI(dis[g[i]], g[i]));
    }
}

int main(int argc, char const* argv[])
{
    IN(n), IN(L), IN(R);
    for (int i = 0; i < n; i += 1) IN(A[i]);
    nth_element(A, A, A + n), n--;
    for (int i = 1; i <= n; i += 1)
        for (int j = 0; j < A[0]; j += 1)
            g.push(j, (j + A[i]) % A[0], A[i]);
    Dij();
    LL ans = 0;
    for (int i = 0; i < A[0]; i += 1)
        if (dis[i] <= R)
        {
            if (dis[i] >= L) ans += (R - dis[i]) / A[0] + 1;
            else
            {
                ans += (R - dis[i]) / A[0];
                ans -= (L - dis[i] - 1) / A[0];
            }
        }
    printf("%lld\n", ans);
    return 0;
}