[Leaf] [P2371] 墨墨的等式

p2371-[国家集训队]-墨墨的等式---洛谷">P2371 [国家集训队] 墨墨的等式 - 洛谷

1. 题面梗概

中译中：给定 $n$ 个硬币面值 $a_i$，问在区间 $[L, R]$ 内，有多少个总和 $B$ 可以由这些硬币凑出来（每个硬币不限次数）。

$n \le 12$，$0 \le a_i \le 5\times 10^5$，$1 \le l \le r \le 10^{12}$。

2. 逻辑推导

每个硬币不限次数是吧，这不就是完全背包裸题吗？等等，这个 $l,r$ 数据规模不对吧，看来得换个方法了。

2.1 模运算

如果一个数 $X$ 能够被凑出来，那么 $X + k \cdot a_i$ 显然也都能凑出来。我们可以选定一个基准面值 $mn = \min \{a_i\}$，将所有整数按模 $mn$ 的余数分成 $mn$ 类。

2.2 建模

定义：$dist[r]$ 为在所有模 $mn$ 余 $r$ 的整数中，能被凑出的最小值。

只要我们求出了 $dist[r]$，那么对于任何整数 $X$，所有满足下面条件的 $Y$ 都可以凑出来：

$$Y \equiv r \pmod{ mn } \quad dist[r] \le Y \le X$$

在范围 $[0, X]$ 内，这类 $Y$ 的个数为：

$$\left\lfloor \frac{X - dist[r]}{mn} \right\rfloor + 1$$

2.3 最短路

• 节点：$0, 1, \dots, mn-1$，代表余数。

• 边：对于每个面值 $a_i$，从余数 $u$ 连向 $(u + a_i) \pmod{mn}$，权值为 $a_i$。

$dist$ 即从 $0$ 出发的单源最短路。

3. 代码实现

▶

AcCode

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 5e5 + 50;
const ll inf = 1e18;

struct State {
    int u; ll d;
    bool operator < ( const State &oth ) const { return d > oth.d; }
};

ll dist[maxn];
bool vis[maxn];
int a[15];
int n, mn;
ll l, r;

void dijkstra( int s )
{
    for( int i = 0; i < mn; ++ i ) dist[i] = inf;
    dist[s] = 0;

    priority_queue< State > pq;
    pq.push({ s, 0 });

    while( !pq.empty( ) )
    {
        auto [u, d] = pq.top( );
        pq.pop( );

        if( vis[u] ) continue;
        vis[u] = 1;

        for( int i = 1; i <= n; ++ i )
        {
            if( a[i] == mn ) continue;
            int v = ( u + a[i] ) % mn;
            if( dist[u] + a[i] < dist[v] )
            {
                dist[v] = dist[u] + a[i];
                pq.push({ v, dist[v] });
            }
        }
    }
}

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

int main( )
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> l >> r;

    mn = 2e9;
    for( int i = 1; i <= n; ++ i )
    {
        cin >> a[i];
        if( a[i] > 0 ) mn = min( mn, a[i] );
    }

    dijkstra( 0 );

    cout << query( r ) - query( l - 1 ) << '\n';
    
    return 0;
}

4. 复盘

• 复杂度分析：$O( n \cdot mn \log mn )$

• 模数的选择：理论上选任何一个 $a_i$ 作为模数都可以，但选 $\min\{a_i\}$ 能让图的点数最少，从而最大化效率。

• 碎碎念：同余最短路 是数论和图论的交界点。这启示我们处理无限的数，可以从处理它们的余数入手。

• 关联笔记：最短路体系 | 降维技巧