bzoj2118 墨墨的等式

发表于

此题非常神地把一个玄学题目强转为图论题目，大意就是说对于 $a_1x_1 + a_2x_2 + \dots + a_nx_n = B$ 当 $B \in [bmin, bmax]$ 是使得方程存在非负整数解的 $B$ 的个数。

显然我们可以求出 $B \in [1, bmax]$ 的答案和 $B \in [1, bmin - 1]$ 的答案做差。

我们发现如果存在 $B$ 使得方程有非负整数解，那么 $B + a_1$ 一定可以使方程有非负整数解。即，我们可以求出当 $B % a_1 = k$ 时使得方程有非负整数解的最小值 $B_0$ ，最后统计答案时全部相加即可。

所以我们对于所有 $k$ 建一个图，共 $a_0$ 个点，编号为 $0$ 到 $a_1 - 1$ 每一个点都有 $n - 1$ 条边，边权分别为 $a_2, a_3,\dots,a_n$ ，对于点 $i$ ，一条边权为 $p$ 的边需要连向点 $(i + p) % a_1$ 。然后以 $0$ 号点为起点，跑一遍最短路，最后点 $i$ 到点 $0$ 的最短路即为在 $B % a_1 = i$ 时的 $B_0$ 。

为什么取 $0$ 号点为起点呢，因为显然 $B % a_1 = 0$ 时的 $B_0 = 0$ ，即所有的未知数都为 $0$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <cstdio>
#include <queue>
#include <algorithm>
#define MAXN 500001

struct Edge {
    struct Node *to;
    struct Edge *next;
    int power;

    Edge(struct Node *to, int power, struct Edge *next) : to(to), power(power), next(next) {}
};

struct Node {
    struct Edge *fe; 
    long long d;

    Node() : fe(0), d(0x7fffffffffffffffLL) {}

    void push(Node *to, int power) {
        fe = new Edge(to, power, fe);
    }
} node[MAXN];

typedef std::pair<long long, Node*> Pair;

int n, a[13];
long long bmin, bmax;

void dijkstra(int s) {
    std::priority_queue<Pair, std::vector<Pair>, std::greater<Pair> > que;
    que.push(std::make_pair(0LL, node + s));
    node[s].d = 0LL;
    
    while(!que.empty()) {
        Node *x = que.top().second;
        que.pop();

        for(Edge *e = x->fe; e; e = e->next) {
            if(e->to->d > x->d + e->power) {
                e->to->d = x->d + e->power;
                que.push(std::make_pair(e->to->d, e->to));
            }
        }
    }
}

int main(int argc, char *argv[]) {
    long long ans = 0;
    scanf("%d%lld%lld", &n, &bmin, &bmax);
    for(int i = 0; i < n; i++) scanf("%d", a + i);

    for(int i = 0; i < a[0]; i++) 
        for(int j = 1; j < n; j++) 
            node[i].push(node + (i + a[j]) % a[0], a[j]);

    dijkstra(0);

    for(int i = 0; i < a[0]; i++) {
        ans = ans + std::max((bmax - node[i].d + a[0]) / a[0], 0LL) - std::max((bmin - node[i].d - 1 + a[0]) / a[0], 0LL);
    }

    printf("%lld", ans);
    return 0;
}