BZOJ 2118 - 墨墨的等式

#数论 #好题 #最短路
Published on 2016-11-07

题目地址

描述

给定 n(n≤12)n(n\le 12)、 、BB 的范围 [L,R](1≤L≤R≤1012)[L, R](1\le L\le R\le {10}^{12})，求有多少个 BB 可以使得方程：

存在非负整数解集。

分析

对于 BB 存在非负整数解，换句话说，就是用任意多个 aia_i，可以凑出 BB 来。

设 mn=min1≤i≤nai\mathrm{mn} = \min_{1\le i\le n} a_i，则我们可以知道，如果 xx 能够凑出来，那么 x+mnx + \mathrm{mn} 也能被凑出来。
如果 y≡x(modmn)y \equiv x \pmod{\mathrm{mn}}，那么 yy 可以凑出所有不小于 yy 且对 mn\mathrm{mn} 取模得 xx 的数。
显然对于每一个 x∈[0,mn)x\in[0, \mathrm{mn})，我们只需要考虑最小的能被凑出的 yy，满足 y≡x(modmn)y \equiv x \pmod{\mathrm{mn}}。我们设对于 xx 来说这个最小的 yy 为 vxv_x。

回到这个题目，不妨设 F(m)F(m) 为 [1,m][1, m] 内的答案，那么求 [L,R][L, R] 内的答案可以转化为 F(R)−F(L−1)F(R) - F(L - 1)。
那么我们现在考虑求 F(m)F(m) 中的答案：考虑从每一个 vxv_x 开始扩展，vxv_x 可以扩展到所有小于等于 mm 且不小于 vxv_x 且对 mn\mathrm{mn} 取模得 xx 的数，所以

F(m)=∑0≤x<mn⌊m−vxmn⌋+1F(m) = \sum_{0\le x<\mathrm{mn}}\lfloor \frac{m - v_x}{\mathrm{mn}}\rfloor + 1

我们来证明这样的扩展方式能够不重不漏的凑出 [1,m][1, m] 中所有能被凑出的数。
不重：如果一个数 nn 能被凑出来，不妨设 nmodmn=rn\bmod \mathrm{mn} = r，因为每一个 vxv_x 只可能更新模 mn\mathrm{mn} 余 xx 的数，所以 nn 只会被 vrv_r 更新，所以没有重复。
不漏：根据我们的计算式，vxv_x 会扩展到所有小于等于 mm 且不小于 vxv_x 且对 mn\mathrm{mn} 取模得 xx 的数。如果 nn 能被凑出来，但是我们没计算到它，不妨设 nmodmn=rn\bmod \mathrm{mn} = r，我们一定可以得到 n<vrn < v_r，这与 vrv_r 的定义矛盾。所以不会遗漏。

问题变成了求 vxv_x，这是一个经典问题，考虑使用最短路求出，建立 mn\mathrm{mn} 个点，点 ii 连出边 (i,(i+aj)modmn,aj),1≤j≤n(i, (i + a_j) \bmod \mathrm{mn}, a_j),1\le j\le n。求出从 00 出发到每个点的最短路 d[]d[]，即得 di=vid_i = v_i。

代码

//  Created by Sengxian on 2016/11/6.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2118 数论 + 最短路
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAX_N = 12, MAX_NODE = 500000 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
typedef pair<ll, int> state;
int n, a[MAX_N], mn;
ll L, R;

inline bool tension(ll &a, const ll &b) {
    return b < a ? a = b, true : false;
}

ll dis[MAX_NODE];
void Dijkstra() {
    priority_queue<state, vector<state>, greater<state> > pq;
    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0;
    pq.push(state(0, 0));
    while (!pq.empty()) {
        state now = pq.top(); pq.pop();
        int u = now.second;
        if (now.first > dis[u]) continue;
        for (int i = 0; i < n; ++i) 
            if (tension(dis[(u + a[i]) % mn], dis[u] + a[i]))
                pq.push(state(dis[(u + a[i]) % mn], (u + a[i]) % mn));
    }
}

inline ll F(const ll m) {
    ll ans = 0;
    for (int i = 0; i < mn; ++i) if (dis[i] <= m)
        ans += (m - dis[i]) / mn + 1;
    return ans;
}

int main() {
    scanf("%d%lld%lld", &n, &L, &R);
    for (int i = 0; i < n; ++i) {
        scanf("%d", a + i);
        if (a[i] == 0) n--, i--;
    }

    mn = *min_element(a, a + n);    
    Dijkstra();

    printf("%lld\n", F(R) - F(L - 1));
    return 0;
}
「NOIP 2009」最优贸易