信息竞赛中的组合数学.ppt

组合数学及其数学构造,曹利国长沙市一中,群,群是集合G和其上的二元运算*,并满足封闭性:对于群里元素a,b,a*b也在G内)结合律:(a*b)*c=a*(b*c)单位元:存在e,对于每个元素a*e=e*a=a逆元:对于每个元素a,存在b使a*b=b*a=e,记b=a-1一般简写a*b为ab,置换,用置换表示1被a1取代,2被a2取代n被an取代.其中a1,a2,an是1n的一个排列,置换群,置换群的元素是置换,运算是置换的连接可以验证置换群满足群的四个条件,循环,n阶循环每个置换都可以写若干互不相交的循环的乘积，例如表示是唯一的.置换的循环节数是上述表示中循环的个数,上例的循环节数是3,传球游戏,n个人围成一圈,每个人编号为1n.有n个球,编号也为1n.一开始每人手里拿一个球基本操作为对传,即a手里的球和b手里的球交换.每个时间单位,一个人可以不做任何动作,或者与另外一人对传目标:每个人拿到和自己编号相同的球问题1:至少需要多少次对传?问题2:至少需要多少时间?,分析,用置换表示初始状态每次对传相当于乘以一个对换置换可以唯一地表示成若干循环的乘积,因此只考虑循环乘以对换(a,b)的结果a和b属于不同循环a个b属于同一个循环,分析,情况一:a和b属于不同循环因为循环的任何一个元素都可写成第一个,不妨设两个循环为(a,a1,a2,an)和(b,b1,b2,bm)结果为(b,b1,b2,bm,a,a1,a2,an)结论:两个循环合并成一个,分析,情况二:a和b属于同一个循环设为(a,a1,a2,ai,b,b1,b2,bm),乘以(a,b)后变为(a,a1,a2,ai)(b,b1,b2,bm)可以这样理解:乘以(a,b)是自身的逆操作结论:一个循环拆为了两个,分析,问题1:由于目标状态是(1)(2)(n),所以需要不断的拆循环.答案为n-c.其中c为轮换个数问题2:结论非常简单循环长度为1,次数为0,显然循环长度为2,次数为1,显然循环长度大于等于3的时候呢?,分析,循环长度大于等于3,次数为2.对于循环(a1,a2,an),只需要乘以(a2,an),就变成了(a1,an)(a2,a3,an-1),再乘以(a3,an-1),就变成了(a2,an-1)(a3,a4,an-2)等等因此只需要乘以(a2,an)(a3,an-1)(a4,an-2)就可以得到(a1,an)(a2,an-1)(a3,an-2)再对换一次就可以了,无聊的排序,你弟弟有一项家庭作业需要你帮助完成。老师给了他一列数，需要他把这些数按升序排列。你可以每次交换两个数的位置，而一次交换的代价被定义成交换的两个数的和。写一个程序，用最小的交换代价和来帮助弟弟完成这项无聊的排序工作。,分析,从初始状态变为目标状态可以看作完成一个置换.把置换分解为s个不相交循环乘积各循环是独立的,所以依次完成各个循环对于任意循环i,设它的长度为ki,容易证明至少需要交换ki-1次,即每次让一个元素到达目标,则前ki-1个元素到达目标后最后一个元素也到达目标,分析,显然每个元素至少参与一次交换.既然交换次数一定,应该让循环中的最小元素ti参加所有交换,其他元素各只参加一次例如(8 2 7),2占了7的位置,则2和7交换;2又占了8的位置,则2和8交换花费为sumi+(ki-2)*ti,其中sumi为第i个循环所有数之和,分析,特殊情况:先让ti和全局最小值m交换,让m进入循环,然后和所有元素交换一次后再和ti交换,花费为sumi+ti+(ki+1)m例如1,8,9,7,6,目标状态为1,6,7,8,9,分解为(1)(8 6 9 7),考虑第二个循环方案一:花费为30+(4-2)*6=42方案二:花费为30+6+(4+1)*1=41,分析,程序实现:只需要记录每个循环节的长度ki和它的最小元素ti,不需要模拟交换找循环最多访问每个元素一次,时间复杂度是线性的,同构计数,一个竞赛图是这样的有向图任两个不同的点u、v之间有且只有一条边不存在自环用P表示对竞赛图顶点的一个置换。当任两个不同顶点u、v间直接相连的边的方向与顶点P(u)、P(v)间的一样时，称该图在置换P下同构对给定的置换P，我们想知道对多少种竞赛图在置换P下同构,同构计数,例：有顶点1、2、3、4和置换P：P(1)=2，P(2)=4，P(3)=3，P(4)=1对于下图的四种竞赛图，在置换P下同构,分析,先把置换它分解成为循环,首先证明长度为L的偶循环将导致无解对于点i1,记P(ik)=ik+1,假设i1和iL/2+1的边方向为i1-iL/2+1,那么有i2-iL/2+2,i3-iL/2+3,iL/2+1-i1,和假设矛盾!假设确定其中k条独立边后其他边也会确定,则答案为2k考虑两类边:循环内边和循环间边.,分析,循环内顶点的关系定了i1和ij之间的关系,ik与i(k+j-2)mod n+1之间的关系也被确定下来了,因此只需要确定i1和i2,i3,i(L-1)/2+1这(L-1)/2对顶点的关系不同循环间顶点的关系设循环为(i1,i2,iL1)和(j1,j2,jL2),通过类似分析得只需要确定gcd(L1,L2)对关系即可,分析,最后答案为2k1+k2其中k1=sum(L-1)/2,k2=sumgcd(L1,L2)可以用二分法加速求幂,Little rooks(SGU 222),中文大意：将k个车摆在n*n的棋盘上，使得任何两个车不能互相攻击（车可以横着或竖着走无限格，不能走斜线），求其放法总数。,算法描述,组合数学：排列与组合,由于题目里的棋子是“车”而不是“后”，所以一个棋子不会影响到与其不同行或与其不同列的棋子。结合n皇后问题的方案表示法，我们很容易想到排列组合。,根据鸽巢原理n=k，先从简单的情况下手：n=k。此时的公式非常简单：P(n,k)。主要就是对于nk的情况时的处理。,因为每一列最多只能放一颗棋子，所以我们首先把没有棋子的列去掉，再合并成一个n*k的棋盘，结合刚才的数据结构我们能很快知道在这个新棋盘上摆k个棋子还是P(n,k)种方案，再把去掉的(n-k+1)列插入摆棋子的k行中，插入方案总数易得为C(n,k)种。,根据乘法原理，总方案数为C(n,k)*P(n,k)种。这样一来程序实现起来就方便多了。,电子锁,某机要部门安装了电子锁。M个工作人员每人发一张磁卡，卡上有开锁的密码特征。为了确保安全，规定至少要有N(=M)个人同时使用各自的磁卡才能将锁打开，并且任意N个人在一起都能将锁打开电子锁上至少要有多少种特征?每个人的磁卡至少要有几个特征?,彩票,大街上到处在卖彩票，一元钱一张。购买撕开它上面的锡箔，你会看到一个漂亮的图案。图案有n种，如果你收集到所有n种彩票，就可以得大奖。请问，在平均情况下，需要买多少张彩票才能得到大奖呢？,分析,已经有k个图案,s=k/n,拿到一个新的需要1次的概率:1-s2次的概率:s*(1-s)t次的概率:st-1*(1-s)期望:概率加权和(1-s)*(1+2s+3s2+4s3+)=(1-s)E而sE=s+2s2+3s3+=E-(1+s+s2+)移项得(1-s)E=1+s+s2+=1/(1-s)=n/(n-k),分析,总结已有0个图案:拿1次就可以多搜集一个已有1个图案:平均拿n/(n-1)次就可多搜集一个已有k个图案:平均拿n/(n-k)次就可多搜集一个所以总次数为:n(1+1/2+1/3+1/n),着色问题,对22的方阵用黑白两种颜色涂色，问能得到多少种不同的图像？经过顺时针旋转能吻合的两种方案算同一种方案,原问题的置换,给四个格子1，2，3，4着k=2种颜色用置换群定义定价类:置换一(转0度)：(1,2,3,4)置换二(转90度)：(2,3,4,1)置换三(转180度)：(3,4,1,2)置换四(转270度)：(4,1,2,3)G=转0度，转90度，转180度，转270度,Burnside引理,对于一个置换f,若方案s变换到自己,称它为f的不动点.f的不动点数目记为C(f)Burnside引理:等价类数目为C(f)的平均值考虑所有满足方案s是置换f的不动点的(s,f)对.则数目=sumCf=sumZk假设有L个等价类,由于处于同一个等价类的Zk相同,因此sumZk中每个等价类可以合并在一起,即sumEk*Zk,其中每个等价类取一个k由基本定理,这个和为L*G.因此L=sumCf/L,Burnside引理计算举例,故方案数为所有C(f)的平均数，即(16+2+4+2)/4=6，和枚举的结果一致,Plya定理,Burnside定理需要计算每个置换f的不动点数目C(f)方案一:对有所有着色方案,检查它是否为f的不动点.缺点:着色方案非常多!方案二:把f分解成循环的乘积.不动点必然满足每个循环内的颜色相同.如果有m(f)个循环,则有km(f)个不动点方案二称为Polya定理,Plya定理计算举例,不同方案数为(24+21+22+21)/4=6,一般情况,n*n的格子,涂m种颜色分n为奇数和偶数两种情况讨论,