2012年noi冬令营曹钦翔讲稿.pptVIP

组合计数与动态规划 北京大学哲学系 曹钦翔 组合计数问题的特征 组合计数是计数问题的一个子类 大量适用于最优化问题的分析手段不适用与组合计数类问题 组合计数问题的特征 A、B是两个集合 已知A，B中元素的最大值，求A∪B的最大值。 已知A，B中元素的和，求A∪B中的元素的和。 组合计数问题的特征 A、B是两个集合 最大值：可以直接求解 和：不可以直接求解 组合计数问题的特征 组合计数问题相比一般计数问题，答案范围通常很大，通常不适用基于枚举的算法 组合计数问题的解答可能会用到一些组合数学的原理和公式 动态规划是组合计数问题最常见的解决方案 组合计数问题的特征 组合计数公式1 在1,2,3,…,n中选出m个，方案总数为： 组合计数公式2 将1,2,3,…,n中分为k组，每组依次包含a1,a2,…,ak个数（a1+a2+…+ak=n），方案总数为： 组合计数公式2 公式推导： 先将n个数排成一列，总方案数为n! 选第1~a1个数形成第一组，因此他们之间的顺序是无关的，故总方案数除以a1！ 选第(a1+1)~(a1+a2)个数形成第二组，因此他们之间的顺序是无关的，故总方案数除以a2！ ……依此类推 组合计数公式2 将1,2,3,…,n中分为k组，每组依次包含a1,a2,…,ak个数（a1+a2+…+ak=n），方案总数为： 组合计数公式2 公式推导： 先从n个数中选出a1个数形成第一组，方案数为：组合数C(n,a1)。 再从剩余的n-a1个数中选出a2个数形成第二组，方案数为：组合数C(n-a1,a2)。 ……依此类推 组合计数公式3 略：等价于公式1 组合计数公式4 公式推导： 设ti=si+(i-1)，即： t1=s1 t2=s2+1 t3=s3+2 … tm=sm+(m-1) 所以：1≤t1t2…tm≤n+m-1。 组合计数公式5 公式推导： 设si=x1+x2+…+xi，即： s1=x1 s2=x1+x2 s3=x1+x2+x3 … sm=x1+x2+…+xm 所以：1≤s1s2…sm-1sm=n。 组合计数公式6~8 请同学们自行推导。 取余数运算的实现 由于组合计数问题的答案通常比较大，题目中往往要求选手输出“答案除以某个数p之后取余数”的结果。 p通常是一个质数，但也有例外。 组合计数过程中，如果涉及除法运算，那么在“取余数”的实现会比较复杂。 取余数运算的实现 涉及加减、乘、除运算，但保证除数与p互质 利用求数论倒数进行除法运算，即： a/b 与 a * b-1 同余 求数论倒数可以在O(p)-O(1)的在线算法，以及每次运算O(logp)的算法。 取余数运算的实现 只涉及乘、除运算，p为质数 把每个数X写成下面形式： X = Y * pn 其中Y与p互质 取余数运算的实现 其他的一些情形： 只涉及乘、除运算，p为合数 涉及加减乘除运算，但是除法运算只有一次 取余数运算的实现 补充：数论倒数b-1的三种求法 利用拓展欧几里得算法求“b*b-1+p*k=1”的一组整数解 当p是质数时，借助公式b-1=bp-2利用快速幂算法求解 当p是质数时，借助“找一个p的原根g”做预处理 计数公式的基本算法 乘方的计算 补充：如何高效的求出1+x+x2+…+xn 组合数的计算 组合计数例题 请同学们踊跃发言 组合计数例题1 搭积木的方案计数。 只允许使用横向放置长度不超过k的长长条形积木，但每一种积木数量不限 只允许在一个1*w底座上进行搭建 每一块积木必须放置在整数位置 每一块积木下方的每一个位置都必须有其他积木或者为底座 搭建的高度不得超过h 组合计数例题1 组合计数例题1 f[i]表示： 积木连接成一条长为i的长条的方案总数 预处理： f[i] = f[i-1] + f[i-2] + … + f[i-k] dp[i][j]表示： 底座长为j，高度出超过i的方案总数 组合计数例题1 状态转移方程： dp[i][j] = dp[i-1][j] * f[j]  + dp[i-1][j-1] * f[j-1] * dp[i][0] + dp[i-1][j-2] * f[j-2] * dp[i][1] + … + dp[i-1][0] * f[0] * dp[i][j-1] 组合计数例题2 现在有n个正方体积木，边长分别是a[1],a[2]…a[n]。 要把他们搭成一座塔（从下到上排成一列），使得所有相邻的两个积木，上方的积木的边长不能比下方的加上D还要大。 输入所有积木的边长，问：有多少种不同的搭建方案。 组合计数例题3 n人参加一次信息学竞赛，共有m道题。 现在比赛已经结束，评分正在进行中 对于已经结束评测的试题，已知每名考生这道题的答案是