PJ3 递推与分治

[TOC]

递推

有些问题中,相邻两项或多项数字(或状态)之间存在某种关系,可以通过前一项或多项按照某一规律推出其后一项数字(或状态),或者是通过后一项或多项按照某一规律推出其前一项数字(或状态)。我们可将这种规律归纳成如下递推关系式:

F_n=g(F_{n-1})或F_{n-1}=g(F_n)

从前状态推出后状态称为顺推,反之称为逆推。分别对应程序中的递推递归

Fibonacci数

嗯,这个很好找,就是:

\begin{cases}
f(0)=0\
f(1)=1\
f(n)=f(n-1)+f(n-2)\quad(n>1)
\end{cases}

int f[maxn];
f[0]=0,f[1]=1;
for(int i=2;i<=n;i++)
    f[i]=f[i-1]+f[i-2]

简单组合计数

基本原理

容斥原理

n+1件东西放入n个抽屉,则至少有一个抽屉里放了两件或两件以上的东西。从另一个角度说,把n-1件东西放入n个抽屉,则至少有一个抽屉是空的。

多个集合的容斥原理

总元素=每个集合加起来-两两交集+三三交集-四四交集+五五交集….etc.

|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

加法原理

如果完成事件An种方法,完成事件Bm种方法,那么完成两者之一有n+m种方法。

乘法原理

如果完成事件An种方法,完成事件Bm种方法,那么先完成A后完成Bn\cdot m种方法。

排列

n个数中有序地取出m个数的方案:

简化:先考虑n个数有几种排列方案

考虑乘法原理,第1个数有n个可能,第2个有n-1个可能,依次类推,所以n个数的排列方案一共有n!

n\times (n-1) \times (n-2) \times (n-3)\times…….\times 1
=n!

n个数中有序地取出m个数的方案

同样考虑乘法原理,第1个数有n种可能,第2个数有n-1种可能,以此类推,一共需要取m个数,所以第m个数有n-m+1种可能。

n\times (n-1)\times(n-2)\times(n-3)\times……\times(n-m+1)\
表示为A^m_n=P^m_n=\frac{n!}{(n-m)!}

组合

n个数中无序地取出m个数的方案:

由于m个数一共有m!种排列方案,所以将A^m_n去掉重复的排列即可,即\displaystyle\frac{A^m_n}{m!}

定义

表示为C^m_n=\frac{A^m_n}{m!}=\frac{n!}{m!(n-m)!}\
也记作C(n,m)

组合数的递推

杨辉三角形

1\
1\quad1\
1\quad2\quad1\
1\quad3\quad3\quad1\
1\quad4\quad6\quad4\quad1\
1\quad5\quad10\quad10\quad5\quad1\
…………………..

我们规定C^0_n=1
则有

1\
C^0_1 \quad C^1_1\
C^0_2 \quad C^1_2 \quad C^2_2\
C^0_3 \quad C^1_3 \quad C^2_3\quad C^3_3 \
C^0_4\quad C^1_4\quad C^2_4\quad C^3_4\quad C^4_4\
…………………..

所以可推出:

C^m_n=C^{m-1}_{n-1}+C^{m}_{n-1}

它的意义:考虑选不选最后一个元素,如果不选他就是C_{n-1}^m,如果选了它,那么就要在剩下n-1个数中选出m-1个,那么就是C_{n-1}^{m-1},两者相加即可

又由杨辉三角形的对称性还可知:

C^m_n=C^{n-m}_n

二项式定理

(a+b)^n=\sum_{i=0}^n C^i_n\times a^i\times b^{n-i}

一些使用二项式定理的常用模型:

\sum_{i=0}^nC_n^i=2^n\tag{1}

\sum_{i=0}^n(-1)^iC_n^i=0\tag{2}

C_n^0+C_n^2+\cdots=C_n^1+C_n^3+\cdots=2^{n-1}\tag{3}

证明:

  1. 由二项式定理,当a=b=1

\begin{aligned}
(1+1)^n&=\sum_{i=0}^n C^i_n\times 1^i\times 1^{n-i}\
2^n&=\sum_{i=0}^nC^i_n
\end{aligned}

  1. 由二项式定理,当a=-1,b=1

\begin{aligned}
(-1+1)^n&=\sum_{i=0}^nC^i_n\times (-1)^i\times 1^{n-i}\
\sum_{i=0}^n (-1)^i C_n^i&=0
\end{aligned}

a=1,b=-1

\begin{aligned}
\left[1+(-1)\right]^n&=\sum_{i=0}^n C_n^i\times 1^i\times (-1)^{n-i}\
\sum_{i=0}^n C_n^i\times (-1)^{n-i}&=0
\end{aligned}

3.

\begin{aligned}
将前面的(1)(2)式相加,得到\
2C_n^0+2C_n^2+\cdots&=2^n\
C_n^0+C_n^2+\cdots&=2^{n-1}
\end{aligned}

同理也可以得到C_n^1+C_n^3+\cdots=2^{n-1}

卡特兰数

现在有n对括号,可以组成多少种合法的括号序列?

合法的括号序列:左右匹配,先左后右

C(n)n对括号时,合法的括号序列的数量

为了区分,我们给每一对括号一个编号

那么假设最后一个右括号是编号为x的,它的总方案数就是

C(x-1)\times C(n-x)

卡特兰数:

\begin{cases}
&C(0)=1\
&C(n)=\sum^{n-1}_{i=0}C(i)\times C(n-i-1), n\geq 1 \
\end{cases}

递推式:

C(n)=\frac{2(2n-1)}{n+1}\times C(n-1)

常见问题变形:

  • n对括号的括号序列数
  • n个数的出栈序列
  • n个点能构成多少种不同的二叉树

递归

递归,就是一个函数调用自己

但是递归很慢。。。。。。而且可能爆栈

但是递归是很多算法和DS的基础,比如二分(当然也可以不用),dfs,线段树,等等等

分治

分治就是分而治之,把一个问题划分成若干个同样的小问题,然后各个击破

我们发现了,分治和递归思想是一脉相承的,大化小,小化了

常见的应用:快速幂,求逆序对等等

最后修改日期: 2020年2月7日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。