P1450 硬币购物

硬币购物：无限制背包与容斥

问题

P1450 硬币购物 - 洛谷
有 $4$ 种固定面值的硬币。每次询问给出每种硬币的数量上限 $d_i$ 和目标金额 $s$，求恰好支付 $s$ 的方案数。

$c_i,d_i,s\le10^5$，询问数不超过 $1000$。

这显然是一道背包问题，于是考虑对原问题的询问单独做一次多重背包，然后我们会发现就 TLE 了。

考虑瓶颈，由于多次询问之间变化的只有每种硬币的数量上限，所以我们可以预处理不限制数量时的支付方案数，然后减去每一次的限制，利用容斥原理。

先忽略所有上限，用完全背包求出 $f[s]$ 表示使用四种硬币凑出金额 $s$ 方案数。

设事件 $E_i$ 表示第 $i$ 种硬币至少使用了 $d_i+1$ 枚。

如果强制事件 $E_i$ 发生，可以先拿出 $d_i+1$ 枚第 $i$ 种硬币。剩余部分仍然可以任意使用四种硬币，所以 $E_i$ 中方案的数量为 $f[s-c_{i}(d_{i} + 1)]$。

更一般地，对于硬币种类集合 $S$，同时要求这些种类超限时，可以预先拿出对应的硬币，方案数为 $\displaystyle f[s-\sum_{i\in S}c_i(d_i+1)]$。

然后我们要求的答案是，全集减去 $E_{0} \cup E_{1} \cup E_{2} \cup E_{3}$，根据容斥原理，我们就可以得到答案，注意加减的关系。

由于硬币种类固定为 $4$，所以只有 $16$ 种情况，所以我们也可以用状压来枚举。

预处理复杂度为 $O(4\cdot mx)$，每次询问为 $O(16\cdot4)$，空间复杂度为 $O(mx+q)$。方案数需要使用 long long。

▶

P1450

struct Query {
    int d[4], s;
};

int c[4];
ll f[maxn];

void solve( ) {
    for( int i = 0; i < 4; ++ i ) c[i] = read( );
    int n = read( );

    vector<Query> qry( n );
    int mx = 0;
    for( int i = 0; i < n; ++ i ) {
        for( int j = 0; j < 4; ++ j ) qry[i].d[j] = read( );
        qry[i].s = read( );
        mx = max( mx, qry[i].s );
    }

    f[0] = 1;
    
    for( int i = 0; i < 4; ++ i ) {
        for( int j = c[i]; j <= mx; ++ j ) {
            f[j] += f[j - c[i]];
        }
    }

    for( auto& q : qry ) {
        ll res = 0;
        for( int mask = 0; mask < (1 << 4); ++ mask ) {
            ll rem = q.s;
            for( int i = 0; i < 4; ++ i ) {
                if( mask & (1 << i) ) rem -= 1ll * c[i] * ( q.d[i] + 1 );
            }
            if( rem < 0 ) continue;
            if( __builtin_popcount( mask ) & 1 ) res -= f[rem];
            else res += f[rem];
        }
        cout << res << '\n';
    }
}

记录

• 新增：当多次询问只改变计数上界时，可以先预处理无限制模型；“至少超限”通过强制拿出若干物品转化回同一个完全背包，再用容斥排除。

• 分类：C