wc组合计数与动态规划.ppt
组合计数与动态规划,北京大学哲学系 曹钦翔,组合计数问题的特征,组合计数是计数问题的一个子类大量适用于最优化问题的分析手段不适用与组合计数类问题,组合计数问题的特征,A、B是两个集合已知A，B中元素的最大值，求AB的最大值。已知A，B中元素的和，求AB中的元素的和。,组合计数问题的特征,A、B是两个集合最大值：可以直接求解和：不可以直接求解,组合计数问题的特征,组合计数问题相比一般计数问题，答案范围通常很大，通常不适用基于枚举的算法组合计数问题的解答可能会用到一些组合数学的原理和公式动态规划是组合计数问题最常见的解决方案,组合计数问题的特征,组合计数公式1,在1,2,3,n中选出m个，方案总数为：,组合计数公式2,将1,2,3,n中分为k组，每组依次包含a1,a2,ak个数（a1+a2+ak=n），方案总数为：,组合计数公式2,公式推导：先将n个数排成一列，总方案数为n!选第1a1个数形成第一组，因此他们之间的顺序是无关的，故总方案数除以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=s1t2=s2+1t3=s3+2tm=sm+(m-1)所以：1t1t2tmn+m-1。,组合计数公式5,公式推导：设si=x1+x2+xi，即：s1=x1s2=x1+x2s3=x1+x2+x3sm=x1+x2+xm所以：1s1s2sm-1sm=n。,组合计数公式68,请同学们自行推导。,取余数运算的实现,由于组合计数问题的答案通常比较大，题目中往往要求选手输出“答案除以某个数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,fi表示：积木连接成一条长为i的长条的方案总数预处理：fi=fi-1+fi-2+fi-kdpij表示：底座长为j，高度出超过i的方案总数,组合计数例题1,状态转移方程：dpij=dpi-1j*fj+dpi-1j-1*fj-1*dpi0+dpi-1j-2*fj-2*dpi1+dpi-10*f0*dpij-1,组合计数例题2,现在有n个正方体积木，边长分别是a1,a2an。要把他们搭成一座塔（从下到上排成一列），使得所有相邻的两个积木，上方的积木的边长不能比下方的加上D还要大。输入所有积木的边长，问：有多少种不同的搭建方案。,组合计数例题3,n人参加一次信息学竞赛，共有m道题。现在比赛已经结束，评分正在进行中对于已经结束评测的试题，已知每名考生这道题的答案是否正确。对于未结束评测的试题，只知道每名考生是否提交答案。每个题分数固定，提交正确的答案的考生可以得到这一题的分数。,组合计数例题3,根据获得的总分进行排名总分越高排名越靠前总分相同时编号较小的考生排名靠前这n人中，排名最靠前的s人将获得候选资格而这s人中将通过最终的科学委员会面试选出其中的t人。,组合计数例题3,输入当前的评测信息，包括：每道题每名选手是否提交已经评测的试题，每名选手是否正确每道题的分值问最终的t人代表队共有多少种组队的可能。,组合计数例题3,思考：对于固定的t个人，问这t人是否有可能组成最终的代表队,组合计数例题3,思考：对于固定的t个人，问这t人是否有可能组成最终的代表队答：这t人按照最高可能得分计算，其他人按照最低可能得分计算。,组合计数例题3,按所有人的最高可能得分排序设I是t人中的得分最低者，前i-1人中有r人，他们即使按照最低得分计算，得分也比I高有i-t人，没有入选最终的t人代表队以上两部分的交集不应该超过s-t人,组合计数例题4,共有n种颜色的“車”放在X*Y的棋盘上每种“車”分别有s1,s2,sn枚问有多少种不同的放置“車”的方式，使得任意两枚不同颜色的“車”都不能相互攻击X,Y=30，n=10,组合计数例题5,有n张双面卡片，在每一张的正面已经写上了1到n，顺序不定，但是每个数必须恰好被写一次。在每一张的反面也已经写上了1到n，也必须每个数恰好被写一次。,组合计数例题5,输入每张卡片正反面写的数问，如果任意安排卡片的顺序，且任意选择每张卡片是正面向上还是反面向上，那么，将这n张牌排成一列，依次将朝上的一面的数读出得到的长度为n的数列，共有多少种不同的可能。,组合计数例题6,输入n,D,L,U。问：一个长度为n的字符串，如果只由数码、大小写字母组成，那么有多少种不同的这样的字符串，其中至少有D个数码、L个小写字母、U个大写字母？n,D,L,U=200000,组合计数例题7,共有n个瞬时事件和m个延时事件。即，每个瞬时事件会在某个时刻发生，每个延时事件会在某个时间开始，然后又在之后的某个时间结束。问：共有多少种不同事件发生的顺序。,组合计数例题8,初始时，序列为：0,1,2,n-1。可以执行的操作有n-1个，分别为：交换第1、2项交换第2、3项交换第n-1、n项已知这n-1个操作每个恰好执行了一次。,组合计数例题8,输入最终的序列问为了达到这种目标序列，共有多少种不同的操作顺序,
