P1450 硬币购物

P1450 [HAOI2008] 硬币购物 ↗

乍一看，是一个多重背包。但是这题“多测”数量大（$n\le 1000$），直接按照多重背包的话，由于是统计方案数而不是求最优，因此无法使用二进制分组和单调队列优化，使用树状数组优化前缀和也只能做到 $O(ns\log s)$，乘上四种硬币的常数，过不了（能拿 10 pts）。

发现这个多测之间有很多公用信息，那就是硬币的面值 $c_i$. 能否预处理出一个只与硬币面值有关的量，从而在每次查询可以快速得出答案？

一开始我是不信的，只是抱着试一试的态度点开了题解区，没想到解题思路立刻到账了。xdm，蓝链还在就是没领完，快去题解区冲冲冲！

完全背包+容斥原理#

第一次做还是很难想到的。

题目其实通过数据范围给我们锁定了一条窄路（当然也可能有神仙奇怪做法），那就是必须根据 $c_i$ 先预处理出一些量，再对快速对每组 $d_i$ 做查询。想想仅仅根据 $c_i$，我们能做什么？

完全背包#

我们可以求解出一个完全背包：在每种硬币数量都无限时，组合出特定钱数 $s$ 的总方案数 $f[s]$.

转移方程 $f[s]+=f[s-c_i]$，枚举每个 $c_i$，再从小到大枚举 $s$.

获得了这个完全背包，我们考虑怎么在给定每个硬币的限制数量 $d_i$ 时，求出满足限制的总方案数。

方案宝宝们#

为了方便理解，这里形式化一下“方案”的定义：

一个方案 $p$ 就是一个四元组 $(x_1,x_2,x_3,x_4)$，其中 $x_i$ 表示第 $i$ 个硬币使用了多少个。两个方案是相同的当且仅当四个分量都相同。

一个方案 $p$ 的钱数 $S(p) = \sum_i c_i x_i$.

那么，我们先前求出的完全背包就是 $f[s] = \lvert \{p \mid S(p) = s\} \rvert$. 为了符号更加清晰，记 $F(s)=\{p \mid S(p) = s\}$.

$F(s)$ 的意思是任何钱数等于 $s$ 的方案组成的集合。我们考虑从中去除不满足要求的部分。

形式化地，一个方案 $p$ 不满足要求，当且仅当 $\exists i \in \{1,2,3,4\},\ x_i > d_i$.

记 $A_i = \{p \mid x_i > d_i\}$，$B_i = A_i \cap F(s)$.

那么符合要求的方案组成的集合就是 $G(s) = F(s) - \bigcup_i A_i$.

容斥原理#

稍加推导：

因此我们要求的就是 $\lvert G(s) \rvert = \lvert F(s) - B_1 - B_2 - B_3 - B_4 \rvert$.

由于 $B_i \subseteq F(s)$，根据容斥原理，$\lvert G(s) \rvert = \lvert F(s) \rvert - \sum_i \lvert B_i \rvert + \sum_{i\ne j} \lvert B_i \cap B_j \rvert - \sum_{i\ne j, j \ne k, i \ne k} \lvert B_i \cap B_j \cap B_k \rvert + \lvert B_1 \cap B_2 \cap B_3 \cap B_4 \rvert$

其中的每一项都可以通过已经求出的 $f[s]$ 数组得到。怎么得到？

$\lvert B_i \rvert$ 表示 $x_i \ge d_i+1$ 且 $S(p)=s$ 的方案数，注意到这个数就等于 $f[s-c_i\times(d_i+1)]$，即 $x_i\ge 0$ 且 $S(p)=s-c_i\times(d_i+1)$ 的方案数。

从完全背包的定义出发可以较为直观地理解这个式子：每种硬币有无限个，组合出钱数 $s$ 的方案数为 $f[s]$，那么要求组合出钱数 $s+c_i\times d$ 且至少使用 $d$ 个第 $i$ 种硬币的方案数，也是 $f[s]$.

同理可以求出交集的元素数：$\lvert B_i \cap B_j \rvert = f[s-c_i\times(d_i+1)-c_j\times(d_j+1)]$.

实现#

二进制枚举子集#

定义集合 $\mathscr{B}=\{B_1, B_2, B_3, B_4\}$，只需要枚举 $\mathscr{B}$ 的子集 $\mathscr{B}_m \in P(\mathscr{B})$，然后把 $(-1)^{\lvert \mathscr{B}_m \rvert} \lvert \bigcap_{B_i \in \mathscr{B}_m} B_i \rvert$ 加到答案里。

可以使用二进制枚举子集技巧，初始化 m=s=(1<<4)-1，然后转移使用 s=(s-1)&m，详见二进制集合操作 ↗. 当然，也可以直接遍历 $s\in\{1,2,\dots,15\}$.

代码#

//
//  main.cpp
//  P1450
//
//  Created by Leo Xia on 2026/4/2.
//

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

using ll = long long;

const int C = 4, S = 100010, N = 1010;

int c[C<<1],n;
int d[N][C<<1],s[N],smx;

ll f[S];

int main()
{
    ios::sync_with_stdio(false);
    cin>>c[1]>>c[2]>>c[3]>>c[4]>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>d[i][1]>>d[i][2]>>d[i][3]>>d[i][4]>>s[i];
        smx=max(smx,s[i]);
    }
    f[0]=1;
    for(int i=1;i<=C;i++)
    {
        for(int j=c[i];j<=smx;j++)
        {
            f[j]+=f[j-c[i]];
        }
    }
    for(int i=1;i<=n;i++)
    {
        ll ans=f[s[i]];
        for(int j=1;j<=15;j++)
        {
            int pcnt=0,ind=s[i];
            for(int k=0;k<4;k++)if(j>>k&1)
            {
                ind-=c[k+1]*(d[i][k+1]+1);
                pcnt^=1;
            }
            if(ind<0)continue;
            ans+=-((pcnt<<1)-1)*f[ind];
        }
        cout<<ans<<'\n';
    }
    return 0;
}

后记#

由于这道题物品种类是常数，所以使用容斥原理的指数级复杂度（枚举子集）没有影响。一般的多重背包是不会考虑这么做的。