NOIP中的数学--第8课容斥原理（一）_信奥教练Andy的博客-程序员秘密

小学数学知识–容斥原理
容斥原理的题目都可以借助韦恩图这一工具来解决，并且非常快速与准确，
一、关于两个集合的容斥原理

集合 A 与B 的并集的元素个数，等于集合 A 的元素个数与集合B 的元素个数的和，减去集合A 与 B 的交的元素个数，即：|A∪B|=|A|+|B|-|A∩B|。
在这里插入图片描述
二、关于三个集合的容斥原理
三个圆A、B、C 分别表示具有三种不同性质的集合，并如图用M1、M2、M3、…、M7 表示由三个圆形成的内部互不重叠的部分所含元素的个数，可见：

｜A∪B∪C｜＝M1＋M2+…＋M7＝（M1＋M4＋M6＋M7）+（M2＋M4＋M5＋M7）+（M3＋M5＋M6＋M7）-[（M4+M7）+（M5+M7）+（M6＋M7）]＋M7＝｜A｜＋｜B｜＋｜C｜-｜A∩B｜-｜B∩C｜-｜A∩C｜+｜A∩B∩C｜
在这里插入图片描述

三、例题点拨

【例1】某班有38名学生，一次数学测验共有两道题，答对第一题的有26人，答对第二题的有24人，两题都答对的有17人，则两题都答错的人数是？（）

A.3 B.5

C.6 D.7

【答案】B

【解析】本题为两集合容斥原理。设两题都答错的人数为x，根据两集合公式，A+B-AB=总个数－都不满足的个数，可得26＋24－17＝38－x，解得x＝5。因此，本题选B。

【例2】某专业有学生50人，现开设有甲、乙、丙三门必修课。有40人选修甲课程，36人选修乙课程，30人选修丙课程，兼选甲、乙两门课程的有28人，兼选甲、丙两门课程的有26人，兼选乙、丙两门课程的有24人，甲、乙、丙三门课程均选的有20人，问三门课程均未选的有多少人？（）

A.1人B.2人

C.3人D.4人

【答案】B

【解析】本题为三集合容斥原理公式1。设三门课均为选的人数为x，根据三集合公式A+B+C-AB-BC-AC+ABC=总个数-都不满足的个数，可得40+36+30-28-26-24+20=50-X，解得X=2。因此选择B选项。

【例3】某乡镇举行运动会，共有长跑、跳远和短跑三个项目。参加长跑的有49人，参加跳远的有36人，参加短跑的有28人，只参加其中两个项目的有13人，参加全部项目的有9人。那么参加该次运动会的总人数为？（）

A.75 B.82

C.88 D.95

【答案】B

【解析】本题为三集合容斥原理公式2，根据三集合公式A+B+C-只满足两个条件的个数-2×满足三个条件的个数=总个数-都不满足的个数，可得参加运动会的总人数为49＋36＋28－13－9×2＝82人。选择B选项。

知识扩展

例题

越狱
【问题分析】
设全集U为所有可能的关押状态所构成的集合，A为所有可能发生越狱的关押状态所构成的集合，那么CuA所有不可能越狱的关押状态所构成的集合。由于|U|=|A|+|CuA|，因此要求|A|。只要求出|U|、|CuA|即可。
再根据乘法原理可知|A|=mⁿ-m(m-1)^n-1.使用快速幂计算即可。
时间复杂度O（logn)
【参考代码】

#include<bits/stdc++.h>
using namespace std;
int qpow(int b,long long e)
{
    
	int ans = 1;
	while(e)
	{
    
		if(e&1)
		{
    
			ans = 1ll*ans*b%100003;
		}
		b=1ll*b*b%100003;
		e>>=1;
	}
	return ans;
}
int main()
{
    
	long long n,m;
	cin>>m>>n;
	int all = qpow(m,n);
	int no=1ll*m*qpow(m-1,n-1)%100003;
	int ans = (all - no)%100003;
	if(ans<0) ans+=100003;//由于取模的原因可能导致ans<0
	cout<<ans<<endl;
	return 0; 
}

本文链接：https://blog.csdn.net/qq_32431299/article/details/113697464

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Qt中实现渐变动画效果_weixin_30673611的博客-程序员秘密

上效果图　　一：思路　　(1).利用QTimer不断的去更新渐变值。　　二：代码实现testwindow.h#ifndef BOXINGBoxingMainWindow_H#define BOXINGBoxingMainWindow_H#include "boxingcircle.h"#include "boxingrectangle.h"#in...

cesium根据缩放层级对应显示点、图片、模型_kalinux的博客-程序员秘密

1，在距离地球30000000米以上显示为点：var point = new Cesium.PointGrapicsvar entity = thie.viewer.entities.add({ p

PHPexcel导出excel时有些数字会变成科学记数法处理方法_php excel导出内容数字变成e+_wuxing164的博客-程序员秘密

#在变量后面加个空格$money .= ' ';

Sgg：Scala语法基础（上）_极度丶浚爱的博客-程序员秘密

Scala语法基础（上）1. 基础语法2 标识符3 变量4 常用类型4.1AnyVal：任意值类型4.2 AnyRef：任意的引用类型4.3 Nothing5 算数操作符重载6 调用函数和方法1. 基础语法Scala 语言是基于 Java 虚拟机运行的，所以基本的语法和 Java 是没有区别的。但是为了简化 Java 的开发以及融合其他的编程语言的优点和特性， Scala 在基本的语法上做了大...

turbojpeg.c 源码_tjflag_bottomup_sandshaw的博客-程序员秘密

QGraphicsView制作绘制图元工具资料整理（鼠标、平移、缩放）_qgraphicsview画多边形_Full_man的博客-程序员秘密

QGraphicsView制作绘制工具资料整理。