《wc2012组合计数与动态规划》由会员分享，可在线阅读，更多相关《wc2012组合计数与动态规划（40页珍藏版）》请在金锄头文库上搜索。
1、组合计数与动态规划北京大学哲学系 曹钦翔组合计数问题的特征n组合计数是计数问题的一个子类n大量适用于最优化问题的分析手段不适 用与组合计数类问题组合计数问题的特征nA、B是两个集合n已知A，B中元素的最大值，求AB的最大值。n已知A，B中元素的和，求AB中的元素的和。组合计数问题的特征nA、B是两个集合n最大值：可以直接求解n和：不可以直接求解组合计数问题的特征n组合计数问题相比一般计数问题，答案 范围通常很大，通常不适用基于枚举的 算法n组合计数问题的解答可能会用到一些组 合数学的原理和公式n动态规划是组合计数问题最常见的解决 方案组合计数问题的特征组合计数公式1n在1,2,3,n中选出m个
2、，方案总数为：组合计数公式2n将1,2,3,n中分为k组，每组依次包含 a1,a2,ak个数（a1+a2+ak=n）， 方案总数为： 组合计数公式2n公式推导：n先将n个数排成一列，总方案数为n!n选第1a1个数形成第一组，因此他们之间 的顺序是无关的，故总方案数除以a1！n选第(a1+1)(a1+a2)个数形成第二组，因 此他们之间的顺序是无关的，故总方案数 除以a2！n依此类推组合计数公式2n将1,2,3,n中分为k组，每组依次包含 a1,a2,ak个数（a1+a2+ak=n）， 方案总数为： 组合计数公式2n公式推导：n先从n个数中选出a1个数形成第一组，方案 数为：组合数C(n,a1)
3、。n再从剩余的n-a1个数中选出a2个数形成第 二组，方案数为：组合数C(n-a1,a2)。n依此类推组合计数公式3n略：等价于公式1组合计数公式4n公式推导：n设ti=si+(i-1)，即：nt1=s1nt2=s2+1nt3=s3+2nntm=sm+(m-1)n所以：1t1t2tmn+m-1。组合计数公式5n公式推导：n设si=x1+x2+xi，即：ns1=x1ns2=x1+x2ns3=x1+x2+x3nnsm=x1+x2+xmn所以：1s1s2sm-1sm=n。组合计数公式68n请同学们自行推导。取余数运算的实现n由于组合计数问题的答案通常比较大， 题目中往往要求选手输出“答案除以某 个数
4、p之后取余数”的结果。np通常是一个质数，但也有例外。n组合计数过程中，如果涉及除法运算， 那么在“取余数”的实现会比较复杂。取余数运算的实现n涉及加减、乘、除运算，但保证除数与 p互质n利用求数论倒数进行除法运算，即：na/b 与 a * b-1 同余n求数论倒数可以在O(p)-O(1)的在线算法， 以及每次运算O(logp)的算法。取余数运算的实现n只涉及乘、除运算，p为质数n把每个数X写成下面形式：nX = Y * pnn其中Y与p互质取余数运算的实现n其他的一些情形：n只涉及乘、除运算，p为合数n涉及加减乘除运算，但是除法运算只有一 次取余数运算的实现n补充：数论倒数b-1的三种求法n
5、利用拓展欧几里得算法求“b*b-1+p*k=1” 的一组整数解n当p是质数时，借助公式b-1=bp-2利用快速 幂算法求解n当p是质数时，借助“找一个p的原根g”做预 处理计数公式的基本算法n乘方的计算n补充：如何高效的求出1+x+x2+xnn组合数的计算组合计数例题n请同学们踊跃发言组合计数例题1n搭积木的方案计数。n只允许使用横向放置长度不超过k的长长条 形积木，但每一种积木数量不限n只允许在一个1*w底座上进行搭建n每一块积木必须放置在整数位置n每一块积木下方的每一个位置都必须有其 他积木或者为底座n搭建的高度不得超过h组合计数例题1组合计数例题1nfi表示：n积木连接成一条长为i的长条
6、的方案总数n预处理：nfi = fi-1 + fi-2 + + fi-kndpij表示：n底座长为j，高度出超过i的方案总数组合计数例题1n状态转移方程：ndpij = dpi-1j * fj + dpi-1j-1 * fj-1 * dpi0+ dpi-1j-2 * fj-2 * dpi1+ + dpi-10 * f0 * dpij-1组合计数例题2n现在有n个正方体积木，边长分别是 a1,a2an。n要把他们搭成一座塔（从下到上排成一 列），使得所有相邻的两个积木，上方 的积木的边长不能比下方的加上D还要 大。n输入所有积木的边长，问：有多少种不 同的搭建方案。组合计数例题3nn人参加一次信
7、息学竞赛，共有m道题 。n现在比赛已经结束，评分正在进行中n对于已经结束评测的试题，已知每名考生 这道题的答案是否正确。n对于未结束评测的试题，只知道每名考生 是否提交答案。n每个题分数固定，提交正确的答案的考 生可以得到这一题的分数。组合计数例题3n根据获得的总分进行排名n总分越高排名越靠前n总分相同时编号较小的考生排名靠前n这n人中，排名最靠前的s人将获得候选 资格n而这s人中将通过最终的科学委员会面 试选出其中的t人。组合计数例题3n输入当前的评测信息，包括：n每道题每名选手是否提交n已经评测的试题，每名选手是否正确n每道题的分值n问最终的t人代表队共有多少种组队的 可能。 组合计数例题
8、3n思考：n对于固定的t个人，问这t人是否有可能组 成最终的代表队组合计数例题3n思考：n对于固定的t个人，问这t人是否有可能组 成最终的代表队n答：n这t人按照最高可能得分计算，其他人按照 最低可能得分计算。组合计数例题3n按所有人的最高可能得分排序n设I是t人中的得分最低者，前i-1人中n有r人，他们即使按照最低得分计算，得分 也比I高n有i-t人，没有入选最终的t人代表队n以上两部分的交集不应该超过s-t人组合计数例题4n共有n种颜色的“車”放在X*Y的棋盘上n每种“車”分别有s1,s2,sn枚n问有多少种不同的放置“車”的方式，使 得任意两枚不同颜色的“車”都不能相互 攻击nX,Y=3
9、0，n=10组合计数例题5n有n张双面卡片，n在每一张的正面已经写上了1到n，顺序不 定，但是每个数必须恰好被写一次。n在每一张的反面也已经写上了1到n ，也必 须每个数恰好被写一次。组合计数例题5n输入每张卡片正反面写的数n问，如果任意安排卡片的顺序，且任意 选择每张卡片是正面向上还是反面向上 ，那么，将这n张牌排成一列，依次将 朝上的一面的数读出得到的长度为n的 数列，共有多少种不同的可能。组合计数例题6n输入n,D,L,U。n问：一个长度为n的字符串，如果只由 数码、大小写字母组成，那么有多少种 不同的这样的字符串，其中至少有D个 数码、L个小写字母、U个大写字母？nn,D,L,U=200000组合计数例题7n共有n个瞬时事件和m个延时事件。即 ，每个瞬时事件会在某个时刻发生，每 个延时事件会在某个时间开始，然后又 在之后的某个时间结束。n问：共有多少种不同事件发生的顺序。组合计数例题8n初始时，序列为：0,1,2,n-1。n可以执行的操作有n-1个，分别为：n交换第1、2项n交换第2、3项nn交换第n-1、n项n已知这n-1个操作每个恰好执行了一次 。组合计数例题8n输入最终的序列n问为了达到这种目标序列，共有多少种 不同的操作顺序
