第6章 组合数学中的程序设计

,第六章 组合数学中的程序设计,沈云付,yfshen,上海大学计算机工程与科学学院,本章主要内容,6.1,组合数学中有关概念与公式,6.1.1,排列与组合及有关的生成算法,6.1.2,母函数,6.1.3,容斥原理与错排,6.1.4,Polya,定理,6.2,实例研究,6.1,组合数学中有关概念与公式,6.1.1,排列与组合及有关的生成算法,1,排列与组合的基本概念和公式,排列、相异元素可重复的排列,组合、相异元素可重复的组合,6.1.1,排列与组合及有关的生成算法,在多项式 的展开式中的项,的系数,不定方程 的有非负整数解的个数为,设,n,是一个正整数，令,Q,n,表示在,1,，,2,，,，,n,中不允许出现两个连续数字的排列方法,数，则有,Q,n,=,6.1.1,排列与组合及有关的生成算法,2,全排列的生成算法,全排列的生成算法有：字典序法、递增进位制数法、递减进位制数法和邻位对换法等,全排列的字典序算法,问题：对于给定的一个全排列,P,，,要生成,P,的下一个排列,Q,6.1.1,排列与组合及有关的生成算法,字典序全排列：,给定,n,个元素的集合,x,1,，,x,2,，,x,3,，,，,x,n,，对,X,中的元素规定了一个先后关系。在两个排列中，按字典序方式对它们的位从左到右每位比较，较小的字符对应的排列较先，按这样的序生成的全排列称为字典序全排列。,给定排列,P,，,求下一个排列,Q,例：求,X=1,，,2,，,3,，,4,，,5,，,6,，,7,上排列,P= 2637541,的下一个排列,Q,从右到左找出比右边数字小的第一个数，即,3,。,再从右到左考察比,3,大的第一个数，是,4,将,3,与,4,对换位置，得,2647531,将得到的排列,2647531,从,4,后面的,7531,翻转得,1357,把前缀,264,接在,1357,的前面得,2641357,，它就是所求的排列,2647531,的下一个排列。,给定排列,P,，,求下一个排列,Q,算法,设,X=1,，,2,，,，,n,，,求,P=a,1,a,2,a,n,的下一个排列：,在,P,中从右到左寻找右边比左边大的数的第一个位置,j,，即,j=,maxi|a,i,a,j,。,此时排列,P,形如,a,1,a,2,a,j-1,a,j,a,j+1,a,k-1,a,k,a,k+1,a,n,。,对换,a,j,，,a,k,，,并将,a,j+1,a,k-1,a,j,a,k+1,a,n,翻转，得,Q= a,1,a,2,a,j-1,a,k,a,n,a,k-1,a,j,a,k+1,a,n,即为,P,的下一个排列。,6.1.1,排列与组合及有关的生成算法,3.,组合的生成算法,令,j= maxi|,a,i,n-m+i+1,。,那么,a,1,a,2,a,m,的下一个组合为,a,1,a,2,a,j-1,(a,j,+1)(a,j,+2)(,a,j,+m-j,),。,例如，给定,n=13,，,m= 6,，,组合,4 5 7 8 12 13,，于是可见,j=3,。将,8 12 13,依次修改为,9 10 11,。那么组合,4 5 7 8 12 13,的下一个组合为,4 5 7 9 10 11,。,6.1.1,排列与组合及有关的生成算法,4.,字典序全排列与序号的转换,字典序全排列的序号,记,P=a,1,a,2,a,n,。记,k,i,为元素,a,i,的逆序数，则排列,P,的序号为,问题：给定排列的序号，如何求全排列？,排列,1 2 3 4 5 8 6 9 7,的,逆序数分别为,0 0 0 0 0 2 0 1 0,，,序号为,345,给定排列的序号,/,给定元素个数,n,，,及全排列,p,/,返回字典序全排列下排列序号,num,int,perm2num(int n,int,*p),int,i, j, num=0,k=1;,for (i=n-2;i=0;k*=n-(i-),/,因子为,(n-i-1)!,，,注意下标从,0,开始,for (j=i+1;jn;j+),if (pj=0;i-)pi=num%(n-i),num/=n-i;,for (i=n-1;i;i-),for (j=i-1;j=0;j-),if (pj=pi) pi+;/,根据逆序数数组进行调整,6.1.1,排列与组合及有关的生成算法,5,字典序组合与序号的转换,实例：设,n,=9,，,m,=4,。,将从,n,个元素取,m,个的所有组合从,1,开始从小到大编序，组合,3 5 7 9,的,序号是多少？,一种计算方法：首位小于,3,的组合的个数为,91,；首位是,3,，第,2,位小于,5,的组合的个数为,10,；前,2,位是,3 5,，第,3,位小于,7,的组合的个数为,3,；前,3,位是,3 5 7,，第,4,位小于,9,的组合的个数为,1,。所有这些数之和,105,，加上它本身的,1,个号，得组合,3 5 7 9,的序号是,106,。,另一种思路由组合求序号,考虑从当前考察的组合的后面有多少个组合。,/,传入,n,、,m,及组合,c,，,返回,c,的序号,num,/,下面的,comb(n,m),是,n,个元素取,m,个的组合数,int,comb2num(int,n,int,m,int,*c),int,num=comb(n,m),i;,for (i=0;im;i+),num = num- comb(n-ci,m-i);,return num;,由序号求组合,由序号求组合算法是前面由组合求序号的逆过程,/,输入,n,、,m,，,序号,num,，,传回所求的组合,c,void num2combA(int,n,int,m,int,*,c,int,num),int,i,j=1,k;,for (i=0;icomb(n-j,m-i-1),num-=comb(n-j,m-i-1),j+;,ci=j;,6.1.2,母函数,母函数：给定序列,a,0,、,a,1,、,a,2,、,、,a,n,、,那么函数,G(x)=,a,0,+,a,1,x,+,a,2,x,2,+,a,k,x,k,+,称为序列,a,0,、,a,1,、,a,2,、,、,a,n,、,的母函数（也叫生成函数）。,给定一个序列，可确定对应的母函数；反过来，给定一个母函数，那么也能确定对应的序列。,例：斐波那契数列,a,n,，,n,=0,，,1,，,2,，,a,0,=,a,1,= 1,，,a,n,=,a,n,-1,+,a,n,-2,。,对应的母函数可表示为,可求得,举例,问题描述,小明手中有,3,张一元,2,张,2,元和,3,张,5,元的钱币,问小明都能买价值为多少的物品？对每种价值的物品他有几种付款方法？如小明手中有,k,张一元，,m,张,2,元和,n,张,5,元的钱币，结果又如何？,输入,输入的第一行是一个整数,T,，（,1,T,10,）,表示测试数据的个数。接下来有,T,行，每行上有,3,个非负整数,k,，,m,，,n,，（,1,k,，,m,，,n,10,），分别表示一元、二元和五元的钱币数。,k,，,m,，,n,中至少有一个非,0,。,输出,对输入中的三种钱币数，输出小明能买物品的价值总数以及所有的付款方法数。,输入,与输出,样例,输入样例,1,3 2 3,输出样例,22 47,对实例的说明,k,=3,，,m=2,，,n=3,一元、二元、五元钱币对应的能买物品的生成函数,小明能买的物品对应的生成函数为,结论,小明可以买价值分别为,0,，,1,，,2,，,21,，,22,元的物品，即,22,种非零的钱数，并且付款的方法数分别为,0,，,1,，,2,，,2,，,2,，,3,，,2,，,3,，,2,，,2,，,3,，,2,，,3,，,2,，,2,，,3,，,2,，,3,，,2,，,2,，,2,，,1,，,1,，总数为,47,。,6.1.3,容斥原理与错排,1,容斥原理,设,A,为任一个有限集合。用,|,A,|,记集合,A,中元素的个数。当,A,为空集时，,|,A,|=0,。,定理,6.1,设,A,，,B,为两个有限集合，那么,定理,6.2,设,A,1,，,A,2,，,，,A,n,是,n,个有限集合，则,2,错排,当,n,1,时，若,n,个元素,1,，,2,，,n,的排列,P,其每个元素都不在原来的位置上（即元素,k,不在位置,k,上），则该排列称为错排。,n,个元素的集合,1,，,2,，,n,的错排个数为,Dn,。,有递推关系,很容易得到关于,Dn,的关系式,Dn,=,3,抽屉原理,将,m,个物品放入,n,个抽屉，则其中至少有一个抽屉里含有 个物品,设,m,1,、,m,2,，,m,1,，,，,m,n,都是正整数，且将,n,个物品放入,n,个抽屉，则：第一个抽屉至少有,m,1,个物品，第二个抽屉至少有,m,2,个物品，,，第,n,个抽屉至少有,m,n,个物品，至少其中之一必定成立。,6.1.4,Plya,定理,群,:,定义,6.3,设,G,是一个集合，,*,是,G,上的二元运算，如果,(,G,，,*,),满足如下条件：,封闭性：对于任何,a,，,b,G,，有,a*b,G,；,结合律：对任何,a,，,b,，,c,G,，,(a*b)*c = a*(b*c),；,单位元：存在,e,G,，,使得对,a,G,，有,a*e=e*a=a,；,逆元：对于每个元素,a,G,，,存在,x,G,，,使得,a*x = x*a = e,。,那么称（,G,，*）,为一个群。,群的例子,例,1,：,设,G=1,-1,，,*,为普通乘法，那么（,G,，,*,）,为一个群，,1,是单位元。,例,2,：,设,G=0,，,1,，,2,，,3,，,，,m-1,，,*,为普通的模,m,加法，那么（,G,，,*,）,为一个群，,0,是单位元。,例,3,：,设,m=10,，记,G=1,，,3,，,7,，,9,，,那么,G,关于模,10,的乘法构成一个群。,子群、交换群,子群：,设（,G,，,*,）是任何一个群，又设,H,是,G,的子集，若（,H,，,*,）是一个群，则称（,H,，,*,）是（,G,，,*,）的一个群，简称,H,是,G,的子群,。,交换群：,设（,G,，,*,）是一个群，如果对于,G,的任何元素,a,，,b,，有,ab,=,ba,，那么称,G,为交换群,。,置换：,设,X,是一个有限集，,是,X,到,X,的一个一一变换，那么称,是,X,上的一个置换。,有限群的阶：,G,的元素个数称为,G,的阶，记为,|,G,|,置换,设,X,是一个有限集，,是,X,到,X,的一个一一变换，那么称,是,X,上的一个置换,：,1,a,1,，,2,a,2,，,，,n,a,n,，,置换的一种记号,注意：上述记号下，同一置换用这样的表示有,n,!,种，但关键的对应关系不变，只有一种。,正三角形,ABC,的变换,正三角形,ABC,的旋转变换和轴对称变换,正三角形的所有变换,沿中心逆时针旋转，有,0,，,120,，,240,三种,旋转,0,，,0,：,A,A,，,B,B,，,C,C,旋转,120,，,1,：,A,C,，,B,A,，,C,B,旋转,240,，,2,：,A,B,，,B,C,，,C,A,沿对称轴翻转,180,，也有三种：,沿,AO,轴翻转，,3,：,A,A,，,B,C,，,C,B,沿,BO,轴翻转，,4,：,A,C,，,B,B,，,C,A,沿,CO,轴翻转，,5,：,A,B,，,B,A,，,C,C,正三角形的所有变换,沿中心逆时针旋转,旋转,0,旋转,120,旋转,240,沿对称轴翻转,180,沿,AO,轴翻转，沿,BO,轴翻转 沿,CO,轴翻转,置换的乘法运算,置换的乘法运算是置换的连接,X,的所有,n!,个置换关于置换的乘法构成一个群,G,，,记为,S,n,，其单位元是,举例：设,3,=,，,2,=,=,3,与,2,的积为置换,5,。,循环,循环,是这样一个置换，满足,：,a,1,a,2,，,a,2,a,3,，,，,a,k,a,1,，,但对其它的元素保持不变，,称为,k,阶循环。,k,阶循环可,记为：,k,称为循环节长度,2,阶循环 也称为对换，简记为（,a1a2,）,置换,与循环,定理,6.3,每个置换都可以写成若干互不相交的循环的乘积，且表示是唯一的。,例：置换 可表示为,(124)(35)(6),，,其循环节数是,3,2,Burnside,引理,定义,6.7,等价：设,G,是有限集,X,上的置换群，点,a,，,b,X,称为“等价”的，当且仅当，存在置换,G,使得,(,a,)=,b,，,记为,a,b,。,轨道：在这种等价关系下，,X,的元素形成的等价类称为,G,的轨道。,a,X,所在的等价类,E,a,，,即为,a,所在的,轨道。,G,的任意两个不同的轨道之交是空集。,等价类：集合,X,上的所有等价类构成,X,的一个划分，等价类的个数记为,L,。,a,不动置换类,Z,a,：设,G,是,X,=1,，,2,，,，,n,上的置换群。若,a,X,，,G,中使,a,保持不变的置换的全体,|,有,G,，,使,(,a,)=,a,，,记为,Z,a,，,叫做,G,中使,a,保持不动的置换类,，简称,a,不动置换类。,性质：对所有,a,X,，,|,Ea,|,Za,|=|,G,|,成立。,证明 略,C,(,),：,对于一个置换,G,，及,a,X,，,若,(,a,)=,a,，,则称,a,为,的不动点。,的不动点的全体记为,C,(,),。,Burnside,引理,证明：略,L,：等价类的个数,|,C,(,),|,：,的不动点的全体的个数,|,Za,|,：,G,中使,a,保持不动的置换类,个数,|G|,：,置换群,G,的元素个数,3,Plya,定理,定理,6.4,设,G=,1,，,2,，,，,t,是,X=a,1,a,2,a,n,上一个置换群，用,m,种颜色对,X,中的元素进行涂色，那么不同的涂色方案数为,其中,Cyc(,k,),是置换,k,的循环节的个数。,证明：略,循环节个数计算,/,输入：一个置换,perm,，,即一个排列,/,返回：置换的最小周期，传回待求置换的循环节个数,num,int,polya(int,*,perm,int,n,int,& num),int,i,j,p,vMAXN=0,cycle=1;,for (num=i=0;in;i+),if (!vi) /vi=0,表示元素,i,尚未处理过,num+; p=i;,for (j=0;!vpermp;j+)/j,记录当前循环节长度,p=permp;,vp=1;,cycle*=,j/gcd(cycle,j,);,return cycle;,6.2,实例研究,6.2.1,蛋糕,6.2.2,杨辉三角形中的奇偶问题,6.2.3,足球赛票,6.2.4,棋盘格数,6.2.5,保险柜上锁,6.2.6,弹球游戏,6.2.7,最少砝码,6.2.8,环,6.2.9,珍珠项链,6.2.10,统计棋局数,6.2.1,蛋糕,问题描述,瓦尔特夫人本周六邀请她的朋友吃晚饭。到那个时候，她想准备一个大的蛋糕。晚饭后，她要把蛋糕切成几块给他们中的每一人。瓦尔特夫人认为如果蛋糕块大小不一样，那么得到小块的客人会不高兴。因此，她将把蛋糕分成如下图所示的形状，即把蛋糕在中间切割。,为使蛋糕更可口，她要用各种不同颜色的果酱涂在上面。要知道，相邻两块是不能有相同颜色的。如果这样的话，她会认为这两块当作一块看待。,她发现，将,2,种果酱放在,3,块蛋糕上是不可能做到的。但如果将,3,种果酱放在,3,块蛋糕上，她发现有,6,种方法。而如果将,4,种果酱放在,3,块蛋糕上，她发现有,24,种方法。现在，瓦尔特夫人对果酱涂在蛋糕上的方法数感兴趣。她需要你的帮助，请你为她编写一个程序进行计算。也许方法数太多，因此瓦尔特夫人只要你告诉她方法数的最后一位数。,注意：因客人不同，下图所示的,2,种方法是不同的。因此你不应混为一谈。,输入,输入有多组测试数据。每一组测试数据由两个整数,m,，,n,组成，其中整数,m,是果酱颜色数，整数,n,是客人数，也是蛋糕块数，,(0,m,100,，,1,n,10 000),。,当输入,m,=,n,=0,时表示输入结束，这种情况你不必处理。,输出,对每种情况，如输入描述中所说，输出将果酱放在蛋糕上的方法数的个位数。,输入与输出样例,输入样例,输出样例,3 3,4 3,4 4,2 3,0 0,6,4,4,0,分析与讨论,令,a,n,表示这,n,块蛋糕用,m,种果酱的的摆设方案数。大蛋糕切成,n,块后的形状如图所示，各块分别标记为,C,1,，,C,2,，,，,C,n,。,分两种情况：,（,1,）,C,1,和,C,n-1,有相同的颜色,（,2,）,C,1,和,C,n-1,有不同的颜色,分析,第一种情况：,C,1,，,C,n-1,颜色相同，,C,n,，,C,1,，,C,2,，,，,C,n-2,有,m,-1,种颜色可用，；而且,C,1,，,C,2,，,，,C,n-2,的着色方案与大蛋糕切成,n,-2,块小蛋糕的着色方案一一对应。此时小蛋糕,C,n,可用,m,-1,种颜色。这种情况，,n,块蛋糕的颜色涂法数为,(,m,-1),a,n-2,。,第二种情况：,C,1,与,C,n-1,颜色不同，,C,n,的颜色可用,m,-2,种。此时,C,1,，,C,2,，,，,C,n-1,的着色方案与大蛋糕切成,n,-1,块小蛋糕的着色方案一一对应。这种情况，,n,块蛋糕的颜色涂法数为,(,m,-2),a,n-1,。,结论：,参考程序,#include ,using namespace std;,int,comput(int,n,int,m),int,i, ret,k=m- 1;,for (ret=1,i=0;imn)&(!(n=0&m=0),cout,comput(n,m,),endl,;,return (0);,6.2.2,杨辉三角形中的奇偶问题,问题描述,在如下所示的杨辉三角形中，第,1,行有,1,个奇数，第,2,行有,2,个奇数，第,3,，,4,，,5,，,6,行分别有,2,，,4,，,2,，,4,个奇数。,1,1 1,1 2 1,1 3 3 1,1 4 6 4 1,1 5 10,10,5 1,1 6 15 20 15 6 1,你的任务：对一般的正整数,n,，,计算杨辉三角形中第,n,行上奇数的个数。,输入与输出,输入,输入有若干行。每一行上有一个正整数,n,，（,1,n,2,32,）。,输入直到文件结束。,输出,对输入文件每行上的正整数,n,，输出杨辉三角形中第,n,行上奇数的个数。,输入样例,输出样例,3,4,8,10,2,4,8,4,分析,在杨辉三角形中，将每行上的奇数用,1,表示、偶数用,0,表示，可得如下的简化的杨辉三角形，其中空白位置对应的行上是数,0,。,构造下页所示的简化杨辉三角形图,图例,有趣的规律,34,行上的,2,个三角形与,12,行上的三角形完全一样；,58,行上稍大的,2,个三角形（底边,4,个,1,）与,14,行上的三角形完全一样；,916,行上再稍大的,2,个三角形（底边,8,个,1,）与,18,行上的三角形完全一样；,第,16,行上,1,的个数是第,8,行上,1,的个数的,2,倍；,第,15,行上,1,的个数是第,7,行上,1,的个数的,2,倍；,第,8,行上,1,的个数是第,4,行上,1,的个数的,2,倍；,第,7,行上,1,的个数是第,3,行上,1,的个数的,2,倍；,计算公式,给定行数,n,，记,m=n-1,的二进制表示为，,用,g(m),表示第,m+1,行上奇数的个数，则,g(m)=2 g( ),另一种分析方法,杨辉三角第,n,行中奇数的项数是二项式 的展开式中系数为奇数的项数。,（,1,）,(,x,+1),n,-1,中系数为奇数的项数,= (,x,+1),n,-1,(mod 2),中系数非,0,的项数；,（,2,）,(,x,+1),2,(mod 2) = (,x,2,+1) (mod 2),（,3,）,(,x,+1),4,(mod 2) = (,x,4,+1) (mod 2),（,4,）,(,x,+1),8,(mod 2) = (,x,8,+1) (mod 2),，,等等,将,n,-1,写为二进制数,a,k,a,k-1,a,1,a,0,，,那么,分析,对等式两边作,mod 2,运算，,丢掉那些使,a,i,=0,的项,(mod 2),。,于是，,(,x,+1),n,-1,中系数为奇数的项数就是所有使,a,i,=1,的项,(mod 2),的乘积展开式中系数为奇数的项数。,结论：杨辉三角形中第,n,行上奇数的个数为,6.2.3,足球赛票,问题描述,一场激烈的足球赛开始前，售票工作正在紧张地进行中。每张球票,为,50,元。现有,2n,个人排队等待购票，其中有,n,个人手持,50,元的钞票，另外,n,个人手持,100,元的钞票，假设开始售票时售票处没有零钱。问这,2n,个人有多少种排队方式，使售票处不至出现找不开钱的局面？,输入,输入的每行上有一个非负整数,n,，（,1,n,1000,）。,输出,对输入每行上的整数,n,，输出这,2,n,个人的排队方式数。,输入与输出样例,输入样例,输出样例,3,4,5,11,分析,令,f(m,n),表示有,m,个人手持,50,元的钞票，,n,个人手持,100,元的钞票时共有的方案总数。,n=0,，,f(m,0 )=1,mn,，,f(m,n)=0,其它，考虑（,m+n,）,个人排队购票,第（,m+n,）,个人手持,100,元的钞票 ：有,f(m,n-1),种,第（,m+n,）,个人手持,50,元的钞票 ：有,f(m-1,n),种,由加法原理得,f,(,m,n,)=,f,(,m,-1,n,)+,f,(,m,n,-1),综合，得：,6.2.4,棋盘格数,问题描述,设有一个方格棋盘，求出该棋盘中包含有多少个正方形、多少个长方形（不包括正方形）。,输入,有若干个棋盘，每个棋盘对应一行上两个整数,n,，,m,，（,l,n,100,，,1,m,100,），,表示有一个,n,m,方格的棋盘。,输出,对输入的,n,m,方格棋盘，输出正方形的个数与长方形的个数。,输入与输出样例,输入样例,输出样例,2 3,6 3,8 10,32 94,分析,先考虑正方形的个数,边长为,k,的正方形个数为,(,n,-,k,+1),(,m-k,+1),。,再考虑长方形（包括正方形）的个数,根据乘法原理，长方形和正方形的个数总计,Total=(1+2+n),( 1+2+m),长宽不等的长方形个数为,Rec_total,= Total- Sq_total,因此，长宽不等的长方形个数为,Rec_total,= Total Sq_total,6.2.5,保险柜上锁,问题描述,有,n,个人组成的委员会负责保管一个保险箱。该委员会经过研究形成决议：委员会中任何,m,个委员同时到场就能打开保险柜，而任何,m,-1,个委员则不能打开保险柜。你的任务是计算至少要给这个保险柜加多少把锁才能满足上述要求。,输入,输入文件中有若干行。每一行上有两个正整数,n,和,m,是一组测试数据，（,1,n,50,，,0,m,n,）。,输入直到文件结束。,输出,对输入文件中的每组测试数据,n,，,m,，,输出满足要求的锁的最少数目。,输入与输出样例,输入样例,输出样例,2 1,5 4,12 5,1,10,495,（,2,）如果取,k,=,，,即加 把锁，那么可以按问题要求向委员们分配钥匙。,现从这两方面考虑：,（,1,）首先确定,k,：,作一个表格可以说明之,分析,设,k,为符合要求的最少的锁的把数。记,A,i,是第,i,个委员可以打开的锁的集合，,A,=1,，,2,，,3,，,，,k,是所有锁的集合。,问题的要求：,A,1,，,A,2,，,，,A,n,中任何,m,个的并是集合,A,，,而任何,m,-1,个集合的并不是集合,A,。,向委员们分配钥匙的一种方案,任意取出,m,-1,列（即取,m,-1,个委员），记为（,j,1,，,j,2,，,，,j,m-1,）。,m,-1,列（,j,1,，,j,2,，,，,j,m-1,）,对应于一个行,row,，,该行上与,m,-1,个列,j,1,，,j,2,，,，,j,m-1,交叉处的格子中都是,0,，而其他格子都是,1,。,将编号为,row,的钥匙分配给编号不是,j,1,，,j,2,，,，,j,m-1,的所有其他委员，即可满足要求。,计算的问题，这是容易的。,A,1,A,2,A,n,1,2,k,6.2.6,弹球游戏,问题描述,有一个三角形容器，上部开一个小口，里面如图中所示按层整齐地放了许多小圆棍作为阻挡物，第,n,层有,n,根阻挡物。,弹球游戏时，小球从容器上部的口子中间处跌落，碰到第一层挡物后等概率地向两侧跌落，碰到与之相邻的第二层两个阻挡物中的一个，再向两侧跌落第三层阻挡物，如此一直下跌最终小球落入底层。,在容器底层放了若干奖品。如下页图所示的,6,层容器中，,A,，,G,区奖品最好，,B,，,F,区奖品次之，,C,，,E,区奖品第三，,D,区奖品最差。为方便起见，约定,A,，,B,，,C,，,D,，,E,，,F,，,G,区分别用,0,，,1,，,2,，,3,，,4,，,5,，,6,区表示。,弹球游戏示意图,一般地，如容器有,n,层，相应地得到不同大小的容器，其底层根据位置不同也放了相应的奖品。该区域奖品的价值与小球落入该区域的概率反向相关，即：区域的概率越大，该区域奖品的价值越小。,你的任务：计算弹球落入某个区域的概率。,输入,输入文件中有若干行。每一行上有两个整数,n,，,m,，（,1,n,65535,，,0,mn,）。,输入直到文件结束。,输出,对输入中每行上的正整数,n,，,m,，,输出弹球落入有,n,层的三角形容器底层中第,m,个区的概率（四舍五入后保留,6,位小数）。,输入与输出样例,输入样例,输出样例,3 2,4 1,8 5,10 3,0.375000,0.250000,0.218750,0.117188,分析,如果,m,=0,或,m,=,n,，,那么小球落入,m,区的概率等于它肩上一个区域概率的,1/2,。,如果,0,m,(3,s-1,),/2,时，,s,-1,个砝码不够。,其中，,i,=0,，,1,或,-1,，（,i=,1,，,2,，,3,，,，,s,）。系数,i,=-1,表示砝码与物体放在同一托盘，系数,i,=1,表示砝码与物体放在不同托盘。,分析,可证，当,a,2,=3,s-1,时，,(,i,=1,，,2,，,3,，,，,s,),，满足 的任何整数,k,都可表示为（*）的形式。,事实上，记,M,=,，,那么,显然，指数在,-,M,与,M,之间的项都出现了。,这表明，当,n,满足 时，所需的砝码为,s,个，可以称出重量,n,，,且表示方式唯一。,6.2.8,环,他在一个环上写了,n,个字母,“,X”,和,“,E”,。,他注意到一些不同的字母序列用循环移动可以变到另一个（这表示这实际上是同一个环形串）。例如，串,“,XXE”-“XEX”-“EXX”,实际上都是相同的。他想知道对于,n,个字母有多少种不同的环形串出现。请您帮助他找出答案。,输入,每行有一个整数,n,，（,1,n,200 000,）。,输出,输出长度为,n,的环形串的个数,输入样例,输出样例,3,4,4,6,分析,环只能顺时针或逆时针旋转,顺时针方向移动,k,个位置等同于逆时针方向转动,n-k,个位置,一共有,n,个置换，记,G=,0,，,1,，,2,，,，,n-1,逆时针旋转,k,个位置，那么,k,=,循环节个数求法,以,n,=8,，,k,=6,时的置换,6,=,为例,考查循环节个数。,易见，,6,=(0642)(1753),有,2,个循环节。,一般情况下，可以证明,k,的循环节个数是,GCD(,n,k,),，因此没有必要构建置换,（或进行分解）,。,长度为,n,的环形串的个数,根据,Plya,定理，长度为,n,的环形串的个数,L=,L,的数目很大，实际编程时需要自己编写计算幂函数,pow(,m,x,),的程序，可能需要用到高精度计算,6.2.9,珍珠项链,问题描述,n,颗红、蓝、绿三种颜色的珍珠串起来形成一个环形项链，（,n 24,）。,如果将沿着中心旋转或者沿对称轴翻转得到的形式认为是相同的，那么有多少种不同的项链形式？,输入,输入有多行，每行一个整数,n,。,最后一行上的,-1,表示输入结束。,输出,对应于输入中的数据,n,，,输出项链有多少种不同的形式。,示例：三色圆环,输入与输出样例,输入样例,输出样例,4,5,-1,21,39,分析,以项链中心顺时针或逆时针旋转，,位置,0,变到位置,i,的旋转可表示为：,i,：,0,i,，,1,i,+1,，,2,i,+2,，,3,i,+3,，,j,(,i,+,j,)%,n,，,，,n,-1,(,i,+(,n,-1)%,n,以项链中心线翻转：,（,1,）,n,为奇数。,此时只有一种形式，即经过某个顶点,i,与中心的连线为轴的翻转,i,，共,n,个；,（,2,）,n,为偶数。,经过某个顶点与中心的连线为轴的翻转，有,n,/2,个；以顶点,i,与,i,+1,的中点与中心的连线为轴的翻转，共,n,/2,个,；,分析,对任何输入的,n,，,恰有,2,n,种不同的置换。,对于各置换的循环节计算，本题的旋转形式的置换,i,，,可直接根据置换的形式算出，循环节长度为,GCD(,i,n,),；,在无法用公式求循环节长度时，根据求循环节长度的程序实现。,以下程序中，给出一个示例，构造所有置换，并用程序计算置换的循环节长度。,求置换,perm,的循环节数,repetend,int,cycle(int,*,perm,int,n,int,&,repetend,),int,i,j,p,vMAXN=0,ret=1;,for (,repetend,=i=0;in;i+),if (!vi),repetend+;p,=i;,for (j=0;!vpermp;j+),p=permp;,vp=1;,ret*=,j/gcd(ret,j,);,return ret;,构造所有置换,double,polya(int,c,int,n)/,旋转和翻转下视为相同,int,i,j,x;double t=0.0,m=c;/c,为颜色数,for (i=0;ii,for (j=0;j=n-1;j+),permj=(i+j)%n;,cycle(perm, n, x);,t=,t+pow(m,x,);,if(n%2=1) /,构造第,i,个翻转,for (i=0;i=n-1;i+)/i,保持不动,for (j=0;j=n-1;j+),perm(i+j)%n=(i-j+n)%n;,cycle(perm, n, x);,t=,t+pow(m,x,);,if(n%2=0),for (i=0;i(n/2);i+)/,构造第,i,个翻转,for (j=0;j=n-1;j+)/i,保持不动，共,n/2,个,perm(i+j)%n=(i-j+n)%n;,cycle(perm, n, x);,t=,t+pow(m,x,);,for (j=0;j=n-1;j+),/i,i+1,，,i-1,i+2,，,，共,n/2,个,perm(i-j+n)%n=(i+j+1)%n;,cycle(perm, n, x);,t=,t+pow(m,x,);,return t/(2*n);,6.2.10,统计棋局数,问题描述,一个有,N,N,个格子的正方形棋盘，每个格子可以用,C,种不同颜色来染色，一共可以得到多少种不同的棋盘。如果一个棋盘，经过任意旋转、反射后变成另一个棋盘，这两个棋盘就是属于同一种棋盘。,比如当,N,=,C,=2,的时候，有如下图所示,6,种不同的棋盘。,现在告诉你,N,和,C,，,请你算算到底有多少种不同的棋盘？,输入,有多组测试数据。每组测试数据包含两个正整数,N,和,C,（,0,N,，,C,1,。,那么,共有,4,个旋转，,2,个沿对角线反射，,2,个沿对边中点连线反射。,若,n,为偶数，则,Total=,若,n,为奇数，则,Total=,未用前页计算公式的程序实现,#define _int64 long long,#define MAXN 4,int,permMAXNMAXN;,int,gcd(int,a,int,b),return,b?gcd(b,a%b):a,;,/,求置换,perm,的循环节数,repetend,int,cycle(int,*,perm,int,n,int,&,repetend,),int,i,j,p,vMAXN=0,ret=1;,for (,repetend,=i=0;in;i+),if (!vi),repetend+;p,=i;,for (j=0;!vpermp;j+),p=permp;,vp=1;,ret*=,j/gcd(ret,j,);,return ret;,/,应用,P,lya,定理，,旋转与反射下视为相同,double,polya(int,c,int,n),int,i,j,x4,NN=n*n;,if (n=1) return c;,double t=0.0,m=c;,for (i=0;i4;i+)/,构造第,i,个旋转，,0,i,for (j=0;j=4;j+) permij=(i+j)%4;,/4,个元素的小置换，分别是转,0,90,180,270,cycle(permi, 4, xi);/,对应于第,i,种转动：转,i*90,NN=(n%2=1)?(NN-1)/4:NN/4;/,用于计算循环节数,for (i=0;i4;i+),xi=xi*NN;/,第,i,种转动的循环节数,if(n%2=1) xi+;/,在奇数时需考虑中心元素,t=,t+pow(m,xi,);,if(n%2=1) t=t+4*,pow(m,(n,*n-n)/2+n);/,反射分解形式相同,else/,沿对角反射与沿对边中点连线反射的分解是不同的,t=t+2*,pow(m,(n,*n-n)/2+n)+2*,pow(m,n,*n/2);,return t/8;,作业,6.1,升降序列,6.5,升降交替数列,6.15,乘积最大,