资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划,从策略到执行的一站式服务

数论

组合数学

六合ssl适用于网站、小程序/APP、API接口等需要进行数据传输应用场景,ssl证书未来市场广阔!成为创新互联的ssl证书销售渠道,可以享受市场价格4-6折优惠!如果有意向欢迎电话联系或者加微信:028-86922220(备注:SSL证书合作)期待与您的合作!

排列与组合

抽屉原理(鸽巢原理)

把n+1个苹果放入n个抽屉里,则至少有一个抽屉放了两个或两个以上的苹果;

从另一个角度来说,把n-1个苹果放入n个抽屉,则至少有一个抽屉是空的。

如果每个抽屉代表一个集合,每一个苹果就可以代表一个元素。

假如有n+1个元素放入n个集合,其中必定有一个集合里至少有两个元素;

把n-1个元素放入n个集合,则至少有一个集合是空的。

通常来说,在问题中,较多的一方就是苹果,较少的一方就是抽屉。

最差原则

即考虑所有可能的情况中,最不利于某件事情 发生的情况。

容斥原理

基本计数原理

分类加法计数原理

做一件事,完成它有 \(n\) 类方法,第一类有 \(m_{1}\) 种,第二类有 \(m_{2}\) 种,……,第 \(n\) 类有 \(m_{n}\) 种,那么完成这件事共有 $ s=m_{1}+m_{2}+…+m_{n}$ 种方法。

特点

分类加法计数原理与分类有关,各种方法相互独立,用其中任一方法都可以完成这件事。

特点是分类独立完成,分类计数。

分步乘法计数原理

做一件事,完成它需要 \(n\) 个先后步骤,做第一步有 \(m_{1}\) 种不同的方法,做第二步有 \(m_{2}\) 种不同的方法,……,做第n步有 \(m_{n}\) 种不同的方法,那么完成这件事共有 \(s=m_{1}×m_{2}×…m_{n}\) 种不同的方法。

特点

分步乘法计数原理与分步有关,各个步骤相互依存,只有各个步骤都完成了,这件事才算完成。

特点是分步依次完成,分步计数。

区别

加法原理是“分类完成”,乘法原理是“分步完成”。

排列与组合

定义

阶乘

\(n!=1×2×…×n\)

\(\left( 0!=1 \right)\)

排列

从n个不同元素中任取m(m<=n)个元素,按照一定的顺序排成一列,叫做从n个不同元素中取出m个元素的一个排列。

对于第一个位置,我们有n种选择;第二个位置,有(n-1)种选择;……;第m个位置,有(n-m+1)种选择;所以,

方案数 \(=n(n- 1)…(n-m+1)\),即

\(m=n\) 时,有 \(A^{n}_{n}=n!\) ,称为 \(n\) 的全排列(n个不同元素全部取出的排列);

\(0 的情况,则称为选排列。

组合

从n个不同元素中,任意取出m(m<=n)个元素并成一组,叫做从n个不同元素中任意取出m个元素的一个组合。

我们考虑从n个物品中选出m个物品的排列,由于在组合中不考虑顺序性,所以每一种组合在排列中重复出现了 \(m!\) 次,所以只需要将排列数除以m!,即

区别

取出的元素与顺序有关的为排列问题,与顺序无关的为组合问题。

公式

该公式是二项式定理,可以证明第三个公式。

Lucas定理

用于求解大组合数取模的问题,其中模数必须为素数。

n%p和m%p一定是小于p的数,可直接求解;

\(C^{m/p}_{n/p}\)可继续用lucas定理求解。这也要求p的范围不能太大,<=\(10^{5}\)左右。

边界条件:当m=0时返回1,即, \(lucas(x,0,p)=1\)

杨辉三角

(a+b)n展开式的二项式系数:

性质

性质1

每行两端都是1,每个数都等于它“肩上”的两个数的和。

性质2

每一行中,与首末两端“等距离”的两个数相等。

性质3

如果二项式的幂指数\(n\)是偶数,则展开中间项\(T_{n/2+1}\)的二项式系数最大;如果\(n\)是奇数,展开的中间两项\(T_{(n+1)/2}\)\(T_{(n+1)/2+1}\)的系数最大。

性质4

二项式每行的系数和等于2n。

组合数求解

用组合数递推公式求解。

复杂度\(O(n^{2})\)

初始条件:

组合数学相关

错排、圆排列

基础数论

取整

x是一个实数,floor(x)为对x向下取整,ceil(x)为对x向上取整。

在c++中,整型变量的除法都是整除的。我们一般考虑除 数为正的情况。若被除数为正,则向下取整;为负则向上取整。

总结,向绝对值小的方向取整。

下取整符号 $\left \lfloor \right \rfloor $

上取整符号 $\left \lceil \right \rceil $

取模

a对b取模得到的结果就是a除以b的余数,记作a mod b。

\(x≡y(\) % \(p)\) 表示x与y对p取模的结果相等,称为同余。

性质

假设x≡y(%p)

x+a≡y+a(%p)

x-a≡y-a(%p)

ax≡ay(%p)

(a+b)%p=(a%p+b%p)%p

(a-b)%p=(a%p–b%p)%p

(a-b)%p=(a-b+p)%p

ab%p=(a%p)(b%p)%p

最大公约数(gcd)/最小公倍数(lcm)

如果a%x=0,我们称x是a的约数(或因数),称a是x的倍数。

a与b的最大公约数,是指一个最大的整数x,使得x同时是a和b的约数。

我们将a与b的最大公约数记作gcd(a,b)。

性质

lcm(a,b)=ab/gcd(a,b)

gcd(a,b,c)=gcd(gcd(a,b),c)

lcm(a,b,c)=lcm(lcm(a,b),c)

欧几里得算法(辗转相除法)

时间复杂度为log级。

算法公式

证明

质数(素数)

一个大于1的自然数,除了1和它本身外,不能被其他自然数整除,这样的数称为质数,否则称为合数。

逆元

对于正整数a,b,如果能找到正整数x使得 \(ax≡1(\) % \(b)\) ,我们称x是a在模b意义下的逆元。

在这里,实际上a与x互为模b意义下的逆元。

由同余方程可知,a在模b意义下存在逆元,当且仅当gcd(a,b)=1,即a与b互质。

在取模的意义下是不能直接作除法的,但利用逆元则可以。

在模意义下,除以一个数,相当于乘上这个数的逆元;或者说乘以一个数,等于除以这个数的逆元。

概率和数学期望

概率

某个事件A发生的可能性的大小,称之为事件A的概率,记作P(A)。

假设某事的所有可能结果有n种,事件A涵盖其中的m 种,那么P(A)=m/n。

如果两个事件A和B所涵盖的结果没有交集(互不相容),那么P(A或B发生)=P(A)+P(B)。

如果A和B所涵盖的结果有交集,那么P(A或B发生)=P(A)+P(B)-P(A与B同时发生)。

记事件B为“事件A不发生”(事件A的对立事件,事件B发生则事件A不会发生)那么P(A)+P(B)=1,即P(B)=1-P(A)。

在两个互不干扰的事中,事件A在其中一件事中,事件B在另外一件事中(独立事件,事件A发生跟B的发生没有关系),那么P(A与B同时发生)=P(A)×P(B)。

数学期望

事件A有多种结果,记其结果为x,那么x的期望值表示事 件A的结果的平均大小,记作E(x)。

E(x)=每种结果与其概率的乘积的和

记两个事件的结果分别为x、y,那么,E(x+y)=E(x)+E(y)

若两个事件互相独立,那么,E(xy)=E(x)·E(y)

若c为常数,那么,E(x+c)=E(x)+c,E(cx)=c·E(x)

并非原创,仅是整理,请见谅


当前题目:数论
文章源于:http://www.cdkjz.cn/article/dsoipog.html
多年建站经验

多一份参考,总有益处

联系快上网,免费获得专属《策划方案》及报价

咨询相关问题或预约面谈,可以通过以下方式与我们联系

大客户专线   成都:13518219792   座机:028-86922220