信奥赛C++提高组csp-s之组合数学专题课：容斥原理详解及案例实践

信奥赛C++提高组csp-s之组合数学专题课：容斥原理详解及案例实践

一、数学原理

容斥原理是一种用于计算多个集合并集元素数量的方法。其核心思想是：先不考虑重叠的情况，把所有包含于各个集合的元素个数加起来，然后再减去重复计算的部分。

对于两个集合A和B，公式为：
∣ A ∪ B ∣ = ∣ A ∣ + ∣ B ∣ − ∣ A ∩ B ∣ |A \cup B| = |A| + |B| - |A \cap B|∣A∪B∣=∣A∣+∣B∣−∣A∩B∣

对于三个集合A、B、C，公式扩展为：
∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ A ∩ B ∩ C ∣ |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

更一般地，对于n个集合，其原理是：奇数个集合的交集加，偶数个集合的交集减。

二、数学例子

1到20的整数中，2或3的倍数的个数

• 令集合A为2的倍数：{2, 4, 6, …, 20}，|A| = 10。
• 令集合B为3的倍数：{3, 6, 9, …, 18}，|B| = 6。
• A∩B既是2的倍数也是3的倍数（即6的倍数）：{6, 12, 18}，|A∩B| = 3。
• 根据容斥原理，2或3的倍数的个数为：|A∪B| = 10 + 6 - 3 = 13 。

三、编程案例：硬币购物

题目描述

共有4 44种硬币。面值分别为c 1 , c 2 , c 3 , c 4 c_1,c_2,c_3,c_4c1​,c2​,c3​,c4​。

某人去商店买东西，去了n nn次，对于每次购买，他带了d i d_idi​枚i ii种硬币，想购买s ss的价值的东西。请问每次有多少种付款方法。

输入格式

输入的第一行是五个整数，分别代表c 1 , c 2 , c 3 , c 4 , n c_1,c_2,c_3,c_4, nc1​,c2​,c3​,c4​,n。

接下来n nn行，每行有五个整数，描述一次购买，分别代表d 1 , d 2 , d 3 , d 4 , s d_1, d_2, d_3, d_4,sd1​,d2​,d3​,d4​,s。

输出格式

对于每次购买，输出一行一个整数代表答案。

输入输出样例 1

输入 1

1 2 5 10 2 3 2 3 1 10 1000 2 2 2 900

输出 1

4 27

数据规模与约定

• 对于100 % 100\%100%的数据，保证1 ≤ c i , d i , s ≤ 10 5 1 \leq c_i, d_i, s \leq 10^51≤ci​,di​,s≤105，1 ≤ n ≤ 1000 1 \leq n \leq 10001≤n≤1000。

思路分析

• 题目分析：
  题目会给出四种面值的硬币，以及每个硬币的数量限制。然后有多次询问，每次询问给定每种硬币的个数限制和一个总金额S，求有多少种付款方式。

  这是一个典型的有限制组合计数问题。如果直接使用多重背包，在面对大量询问时会超时。这里需要巧妙地运用容斥原理。

  1. 理想情况：不考虑每种硬币的数量限制，即每种硬币都有无限个。这就变成了一个完全背包问题，我们可以预处理出总价为i的方案数f[i]。
  2. 加入限制：对于第j种硬币，其数量限制为d[j]。这意味着我们不能使用超过d[j]个这种硬币。那么，不合法的方案就是至少使用d[j] + 1个这种硬币的方案。
  3. 容斥计算：总方案数（无限制） - (硬币1超限 ∪ 硬币2超限 ∪ 硬币3超限 ∪ 硬币4超限) 的方案数。
     根据容斥原理，这个并集的大小等于：
     • 单个硬币超限的方案数之和
     • 减去两个硬币同时超限的方案数
     • 加上三个硬币同时超限的方案数
     • 减去四个硬币同时超限的方案数
  4. 如何计算"某几个硬币超限"的方案？如果我们要强制第i种硬币至少使用d[i]+1个，我们可以预先从总金额S中减去这些强制使用的金额，即S - (d[i]+1)*c[i]。剩下的金额在无限制的情况下任意组合，方案数就是f[S - (d[i]+1)*c[i]]。如果剩余金额为负数，则方案数为0 。

  代码实现

  #include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=1e5+5;ll f[N];// f[i]: 在不考虑每种硬币数量限制的情况下，凑成总面值 i 的方案数intc[5],d[5];// c[]: 四种硬币的面值, d[]: 四种硬币的数量限制intm,s;// m: 询问次数, s: 每次询问的总金额// 简洁的DP预处理函数voidinit(){f[0]=1;// 凑0元有1种方案：什么都不选// 完全背包：遍历每种硬币for(inti=1;i<=4;i++){// 正序遍历金额，因为每个硬币可以无限使用for(intj=c[i];j<N;j++){f[j]+=f[j-c[i]];}}}// 简洁的容斥计算函数// 参数：传入一个位掩码，代表当前要强制哪些硬币超限// 返回值：这种超限组合下的方案数llcal(intmask){ll sum=s;// 剩余金额，初始为总金额intcnt=0;// 记录强制超限的硬币数量，用于判断容斥系数的正负// 遍历四种硬币for(inti=1;i<=4;i++){// 如果 mask 的第 i-1 位是1，表示要强制第 i 种硬币超限if(mask>>(i-1)&1){// 减去强制使用的 (d[i]+1) 个硬币的总面值sum-=1ll*(d[i]+1)*c[i];cnt++;// 超限硬币数加1}}// 如果剩余金额为负数，方案数为0if(sum<0)return0;// 根据容斥原理：奇数个集合加，偶数个集合减// 这里 cnt 代表我们正在计算的交集大小，所以 cnt 为奇数要加（容斥系数+1），为偶数要减（容斥系数-1）// 我们返回值是 ( -1)^{cnt+1} * f[sum] ? 不对，我们应该返回的是 f[sum] * 符号系数。// 在最终的 ans 中，我们累加的是 (cnt%2==1 ? -1 : 1) * f[sum]。// 因为 ans = 总方案(全不选，cnt=0, 系数为+1) - (单超限，cnt=1, 系数为-1) + (双超限，cnt=2, 系数为+1) ...// 所以 cnt 为奇数时，系数应为 -1；cnt 为偶数时，系数应为 +1。return(cnt&1)?-f[sum]:f[sum];}intmain(){// 读入四种硬币的面值for(inti=1;i<=4;i++)scanf("%d",&c[i]);scanf("%d",&m);init();// 预处理完全背包while(m--){// 读入四种硬币的数量限制和总金额for(inti=1;i<=4;i++)scanf("%d",&d[i]);scanf("%d",&s);ll ans=0;// 最终答案// 枚举所有子集 (2^4 = 16 种状态)// mask 从 0 到 15，代表哪些硬币被强制超限for(intmask=0;mask<16;mask++){ans+=cal(mask);// 累加每种情况下的容斥贡献}printf("%lld\n",ans);}return0;}

  功能分析

  • init(): 这个函数通过完全背包算法，预处理出在无限硬币情况下，凑成任意金额j的方案数f[j]。这是后续所有容斥计算的基础。
  • cal(mask): 这个函数是容斥逻辑的核心。它接收一个二进制掩码mask，例如mask=3（二进制0011）代表强制第1种和第2种硬币超限。
    1. 首先，从总金额s中减去所有强制超限硬币的总价值(d[i]+1)*c[i]。
    2. 如果剩余金额为负，说明这种超限情况不可能发生，返回0。
    3. 否则，根据强制超限的硬币数量cnt决定返回+f[sum]还是-f[sum]。这直接对应了容斥原理的加减号规则。
  • main(): 读入数据，调用init()。对于每个询问，遍历所有16种超限情况的组合，累加cal(mask)的返回值。最终累加结果ans就是经过容斥修正后的合法方案数。这种方法将每个询问的复杂度从指数级背包降为了常数级（16次循环），极大地提高了效率。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}