tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 数学 >>

曹钦翔


组合计数与动态规划
北京大学哲学系 曹钦翔

组合计数问题的特征
组合计数是计数问题的一个子类 大量适用于最优化问题的分析手段不适 用与组合计数类问题

组合计数问题的特征
A、B是两个集合
已知A,B中元素的最大值,求A∪B的最大值。 已知A,B中元素的和,求A∪B中的元素的和。

组合计数问题的特征
A、B是两个集合
最大值:可以直接求解 和:不可以直接求解

组合计数问题的特征
组合计数问题相比一般计数问题,答案 范围通常很大,通常不适用基于枚举的 算法 组合计数问题的解答可能会用到一些组 合数学的原理和公式 动态规划是组合计数问题最常见的解决 方案

组合计数问题的特征

组合计数公式1 组合计数公式
在1,2,3,…,n中选出m个,方案总数为:

C

m n

组合计数公式2 组合计数公式
将1,2,3,…,n中分为k组,每组依次包含 a1,a2,…,ak个数(a1+a2+…+ak=n), 方案总数为:

n! a1!?a 2 !?... ? a k !

组合计数公式2 组合计数公式
公式推导:
先将n个数排成一列,总方案数为n! 选第1~a1个数形成第一组,因此他们之间的 顺序是无关的,故总方案数除以a1! 选第(a1+1)~(a1+a2)个数形成第二组,因此 他们之间的顺序是无关的,故总方案数除以 a2! ……依此类推

组合计数公式2 组合计数公式
将1,2,3,…,n中分为k组,每组依次包含 a1,a2,…,ak个数(a1+a2+…+ak=n), 方案总数为:

C ?C
a1 n

a2 n ? a1

? ... ? C

ak n ? a1 ? a 2 ...? a k ?1

组合计数公式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≤t1<t2<…<tm≤n+m-1。

组合计数公式5 组合计数公式
公式推导:
设si=x1+x2+…+xi,即:
s1=x1 s2=x1+x2 s3=x1+x2+x3 … sm=x1+x2+…+xm

所以:1≤s1<s2<…<sm-1<sm=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道题。 现在比赛已经结束,评分正在进行中
对于已经结束评测的试题,已知每名考生 这道题的答案是否正确。 对于未结束评测的试题,只知道每名考生 是否提交答案。

每个题分数固定,提交正确的答案的考 生可以得到这一题的分数。

组合计数例题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的棋盘 上
每种“車”分别有s[1],s[2],…,s[n]枚

问有多少种不同的放置“車”的方式, 使得任意两枚不同颜色的“車”都不能 相互攻击 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 组合计数例题
输入最终的序列 问为了达到这种目标序列,共有多少种 不同的操作顺序



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com