BZOJ 2118 / 同余最短路

Posted on 2019-10-28 Edited on 2019-12-08 Views:

本地笔记整理重发，原文写于2019/10/28，2019/12/8上传

题面

题意：求使得关于 $\{x_i\}$ 的方程

$\sum_{i=1}^n a_ix_i = b$

存在非负整数解的的 $b \in [l, r]$ 的个数。

数据范围： $n \le 12, a_i \le 5\times 10^5, l, r \in 10^{12}$ 。

神题。不妨设 a_1 为 $\{a_i\}$ 当中的最小值。则若对于任意的 $b \equiv x \pmod{a_1}$ 当中的如果符合题意有解，那么 b+a_1 也一定有解。令满足这个性质的最小的为 b_x 。

考虑在此条件下如何计算解的数目，设以下满足题意的有 f(m) 个，则可以得出计算式：

$f(m) = \sum_{x=0}^{a_1-1} [b_x \le m]\left(\left\lfloor\frac{m-b_x}{a_1}\right\rfloor+1\right)$

原理显然。

答案就是 f(r) - f(l - 1) 。

接下来考虑如何求取 b_x 。考虑构建具有 a_1 个点，编号分别为 $0,1,2,\cdots,a_1 - 1$ 的图，对于编号的点，向 $(u + a_i) \bmod a_1, \ (i=2,3,\cdots, n)$ 连边。表示在模 a_1 意义下，如果可以有解，那么 u+a_i 也一定有解。

由于是一定有平凡解的，我们从开始跑最短路，就可以求出 b_x 。这背后的思想无疑是非常巧妙的。

复杂度就是 $\mathcal{O}(na_1(\log n + \log a_1))$ ，即为Dijkstra的复杂度。

代码

#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
const int N = 13;
const int V = 500010;
const int E = N * V;
const ll INF = 1ll << 60;
ll n, Bl, Br, a[N], mn, len[E];
int fst[V], nxt[E], to[E], tot = 1;
ll dis[V];
void link(int u, int v, ll w) {
    nxt[++tot] = fst[u];
    fst[u] = tot; to[tot] = v; len[tot] = w;
}
void dijkstra() {
    static priority_queue<pli, vector<pli>, greater<pli> > q;
    fill(dis, dis + mn, INF);
    dis[0] = 0; q.push(make_pair(0, 0));
    while (!q.empty()) {
        pli p = q.top(); q.pop();
        int u = p.second;
        if (dis[u] != p.first) continue;
        for (int e = fst[u]; e; e = nxt[e]) {
            int v = to[e];
            if (dis[v] > dis[u] + len[e]) {
                dis[v] = dis[u] + len[e];
                q.push(make_pair(dis[v], v));
            }
        }
    }
}
ll calc(ll x) {
    ll ans = 0;
    for (int i = 0; i < mn; i++)
        if (x >= dis[i]) ans += (x - dis[i]) / mn + 1;
    return ans;
}
int main() {
    scanf("%lld%lld%lld", &n, &Bl, &Br);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    sort(a + 1, a + 1 + n); mn = a[1];
    for (int i = 0; i < mn; i++)
        for (int j = 2; j <= n; j++)
            link(i, (i + a[j]) % mn, a[j]);
    dijkstra();
    printf("%lld\n", calc(Br) - calc(Bl - 1));  
    return 0;
}