曹钦翔wc2012组合计数与动态规划

《曹钦翔wc2012组合计数与动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合计数与动态规划北京大学哲学系曹钦翔组合计数问题的特征组合计数是计数问题的一个子类大量适用于最优化问题的分析手段不适用与组合计数类问题组合计数问题的特征A、B是两个集合已知A，B中元素的最大值，求A∪B的最大值。已知A，B中元素的和，求A∪B中的元素的和。组合计数问题的特征A、B是两个集合最大值：可以直接求解和：不可以直接求解组合计数问题的特征组合计数问题相比一般计数问题，答案范围通常很大，通常不适用基于枚举的算法组合计数问题的解答可能会用到一些组合数学的原理和公式动态规划是组合计数问题最常见的解决方案组合计数问题的特征组合计数公式1在1,2,3,…,n中选出m个，方案总

2、数为：组合计数公式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,

3、a1)。再从剩余的n-a1个数中选出a2个数形成第二组，方案数为：组合数C(n-a1,a2)。……依此类推组合计数公式3略：等价于公式1组合计数公式4公式推导：设ti=si+(i-1)，即：t1=s1t2=s2+1t3=s3+2…tm=sm+(m-1)所以：1≤t1

4、输出“答案除以某个数p之后取余数”的结果。p通常是一个质数，但也有例外。组合计数过程中，如果涉及除法运算，那么在“取余数”的实现会比较复杂。取余数运算的实现涉及加减、乘、除运算，但保证除数与p互质利用求数论倒数进行除法运算，即：a/b与a*b-1同余求数论倒数可以在O(p)-O(1)的在线算法，以及每次运算O(logp)的算法。取余数运算的实现只涉及乘、除运算，p为质数把每个数X写成下面形式：X=Y*pn其中Y与p互质取余数运算的实现其他的一些情形：只涉及乘、除运算，p为合数涉及加减乘除运算，但是除法运算只有一次取余数运算的实现补充：数论倒数b-1的三种求法利用拓展欧几里得

5、算法求“b*b-1+p*k=1”的一组整数解当p是质数时，借助公式b-1=bp-2利用快速幂算法求解当p是质数时，借助“找一个p的原根g”做预处理计数公式的基本算法乘方的计算补充：如何高效的求出1+x+x2+…+xn组合数的计算组合计数例题请同学们踊跃发言组合计数例题1搭积木的方案计数。只允许使用横向放置长度不超过k的长长条形积木，但每一种积木数量不限只允许在一个1*w底座上进行搭建每一块积木必须放置在整数位置每一块积木下方的每一个位置都必须有其他积木或者为底座搭建的高度不得超过h组合计数例题1组合计数例题1f[i]表示：积木连接成一条长为i的长条的方案总数预处理：f[i]

6、=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还要大。输入所有积木的边长，问：有多少种不同的

7、搭建方案。组合计数例题3n人参加一次信息学竞赛，共有m道题。现在比赛已经结束，评分正在进行中对于已经结束评测的试题，已知每名考生这道题的答案是否正确。对于未结束评测的试题，只知道每名考生是否提交答案。每个题分数固定，提交正确的答案的考生可以得到这一题的分数。组合计数例题3根据获得的总分进行排名总分越高排名越靠前总分相同时编号较小的考生排名靠前这n人中，排名最靠前的s人将获得候选资格而这s人中将通过最终的科学委员会面试选出其中的t人。组合计数例题3输入当前的评测信息，包括：每道题每名选手是否提交已经评测的试题，每名选