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 组合计数例题
输入最终的序列 问为了达到这种目标序列,共有多少种 不同的操作顺序


推荐相关:

noi论文分类

《解析一类组合游戏》 2009 - 曹钦翔《从“k 倍动态减法游戏”出发探究一类组合游戏问题》 2009 - 方展鹏《浅谈如何解决不平等博弈问题》 2009 - 贾志豪《组合...


自动控制设计

曹钦翔_wc2012组合计数与... 40页 免费 电机设计论文 79页 2下载券 基于单片机的智能台灯毕... 33页 4下载券 STC 12C5A16S2 性能摘要... 4页 1下载券自...


2008TICupWinners

曹钦翔 毛杰申 陆奕骞 陈晟伟 刘王赢伟 郭嘉骅 叶云飞 沈之默 李观群 朱靓妤 蒋译瑶 姜雨晨 陈睿源 罗珞 龚博易 周昭奕 李汉平 沈楚雄 20 21 22 23 24...

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