数论2


数论2


排列组合

  • 加法原理:p1+p2+p3+..+pn;
  • 乘法原理:p1xp2xp3x..xpn;
  • 容斥原理:|AUBUC|=|A|+|B|+|C|-|AnB|-|BnC|-|AnC|+|AnBnC|;

杨辉三角

根据杨辉三角我们可以与二项式定理进行比较得出一个有趣的结论:(a+b)^n的展开项系数和杨辉三角的行数系数相对应,因此当已知n要求展开项的时候我们可以采取递推或者直接推算的方法。其中前一个是o(n^2)后一个是o(n)。

void calc1()
{
	memset(c,0,sizeof(c));
	for(int i=0;i<=n;i++)
	{
		c[i][0]=1;
		for(int j=0;j<=i;j++)
			c[i][j]=c[i][j-1]+c[i-1][j-1];
	}
}
void calc2()
{
	f[0]=1;
	for(int i=1;i<=n;i++)
		f[i]=f[i-1]*(n-i+1)/i;
}

约数个数

求正整数n的正约数的个数:

首先直接进行求唯一分解式:n=p1^a1xp2^a2xp3^a3xpn^an,接下来就可以直接推出答案ans=(a1+1)x(a2+1)x…x(an+1)


欧拉函数

求与正整数n互素的数的个数:

假设一个正整数n与正整数k不互素,同时n>k,那么k的x倍(xk<n)都与n不互素,因此只要减去与之不互素的数和它的倍数即可,可以推出公式:φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pk)

int phi(int n)
{
	int ans=n,m=(int)sqrt(n+0.5);
	for(int i=2;i<=m;i++)
		if(n%i==0){
			ans=ans*(i-1)/i;
			while(n%i==0)	n/=i;
		}
	if(n>1)	ans=ans*(n-1)/n;
	return ans;
}

欧拉函数的线性筛,时间复杂度是O(nloglogn):

void f(int n)
{
	for(int i=2;i<=n;i++)	phi[i]=0;
	phi[1]=1;
	for(int i=2;i<=n;i++)
		if(!phi[i])
			for(int j=i;j<=n;j+=i){
				if(!phi[j])	phi[j]=j;
				phi[j]=phi[j]*(i-1)/i;
			}
}

编解码

之前提到的字典序的全排列问题,我们用while(next_permutation)去打印所有的全排列,但是引出了一个问题,我们可否根据一个任意的字符串来求出他是第几个全排列,或者反之直接求出第n个序列,这时候就可以用上我们的编解码了。

假设一个字符串由aabc组成,我们讨论它编码的问题,设d(s)代表小于s的串的个数,f(s)代表s的全排列数量,比如现在求caba在aabc全排列的位置,我们就可以通过下面的图来解释,那么f(s)怎么求,我们用组合数学的公式,设字符共有k类,个数分别是n1,n2…nk个,那么f(s)=(n1+n2+…+nk)!/n1!n2!…nk!。同样的解码问题可以引申为下图的右侧。


离散概率

这真算是离散数学的开端了,就直接介绍几个简单的概率问题:

样本空间

设所有会发生的事情是样本空间|S|然后会发生的事件为|E|,直接求出答案:P(E)=|E|/|S|。

补集概念

有时候正向求概率的时候不容易推导,我们用求1-k的方式去求解,但是在算的时候要注意double的范围问题,推荐用边乘边除的方式:

P(E)=1-P(/E)=1-P(E1)P(E2)P(E3)……P(En)=1-n/nx(n-1)/nx(n-2)/n……(n-(m-1))/n。

条件概率

B事件发生的情况下A的概率:P(A|B)=P(AB)/P(B)

全概率公式

P(A)=P(A|B1)xP(B1)+P(A|B2)xP(B2)+…+P(A|Bn)xP(Bn)

贝叶斯公式

P(A|B)=P(A)/(P(A|B1)xP(B1)+P(A|B2)xP(B2)+…+P(A|Bn)xP(Bn))



文章作者: Dydong
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Dydong !
  目录