ACM竞赛中的数学方法初步

ACM竞赛中的数学方法初步曾强2006-7-7计算几何所谓计算几何,一般就指向量方法来解几何问题.为什么用向量?因为解析几何方法在很多时候都显得复杂,而且计算可能比较复杂,有精度损失问题.坐标法基础计算几何都是以坐标化为前提的必须知道一些基本的解析几何的方法.例如:两点距离的公式等向量的点积向量a,b点积(又称内积)的几何意义是a在b(或b在a)上的投影长度(标量,注意可能为负值).计算方法是a·b=|a|·|b|·cosC,其中,C是向量a,b的夹角(下同).若向量a=(x1,y1,z1),b=(x2,y2,z2),则a·b=x1x2+y1y2+z1z2cosC可以由此计算出来应用用于计算向量夹角.判断两向量是否垂直平面方程的向量形式:平面方程ax+by+cz=0(已通过移坐标轴去掉常数项),令平面法向量n=(a,b,c),点X(x,y,z),则平面方程记为n·X=0,实际上,如果平面过点P,则方程为n·(X-P)=0.应用(续)还可以计算点P(x0,y0,z0)到平面n·X=0的距离.把n单位化,不妨仍记为n,把向量OP往n上投影,即可得距离d=|n·OP|.判断P是否在平面的哪一边:n·OP为正时P在n指向的一侧,否则与n的指向相反向量叉积叉积又称外积,a×b的结果是一个矢量,其数值是以a,b为边的平行四边形面积,即|a||b|sinC,其方向和a,b都垂直,并且,a,b,a×b构成右手系.计算方法:应用计算三角形或者平行四边形面积计算点到直线(进一步,线段)的距离判断向量(或者直线,线段)平行关系内积和外积结合可以判断复杂的位置关系点的旋转变换原来的点(x,y)和变换后的点(x’,y’)的坐标之间满足下面的公式: x’=xcosθ-ysin

θ y’=xsin

θ+ycos

θ其中,θ是逆时针旋转的角度,这个公式适用于旋转点在原点的情况.球面距离已知球半径R,球面上两点A,B的坐标A(x1,y1,z1),B(x2,y2,z2),球心在原点O,球面距离已知两点的极坐标,其中, 为经度数, 为纬度数,则可以证明球面距离为极坐标与直角坐标之间的换算关系:其中,θ是纬度,φ是经度已知极坐标,也可以先用上面的公式计算直角坐标,然后算球面距离,但是会有精度损失计算几何进一步的话题内容很丰富,以上列举的是基本的武器参加ACM竞赛至少还需要了解二维凸包的算法(比较复杂)例题BOJ1012TheCircumferenceoftheCircle给出了三个点的坐标，请输出由这三个点所确定的圆的周长，结果保留二位小数如图,关键是求出外接圆半径RABC可以由向量外积算出面积s,并得到sinA.由正弦定理,a/sinA=2R由此可以计算外接圆面积ABCabcBOJ1062PolygonProgrammingwithEase给了n边形的n条边的中点,求n个顶点的坐标,n是奇数可以建立两个(x坐标和y坐标)联系n个顶点和n个中点的n元一次方程组,注意到n是奇数,这样的方程有唯一解另一种思路可以证明以下事实:将一个n边形依次以其每边中点为对称中心做中心对称(反射)变换,n次变换之后,等价于对此多边形做了一个以第一个顶点为中心,180度的旋转变换.可以任意选定一个点p,依次对每个中心做反射变换,n次之后得到q,则第一个顶点是(p+q)/2,由此可以得到其它顶点BOJ1054Equidistance给定球面两点A,B的极坐标,再给定第三点P的极坐标,求球面上到A,B两点距离相等的点(组成一个大圆O1)到P点的最短球面距离首先,把极坐标转换成直角坐标.以a,b,p代表A,B,P对应的向量.到A,B距离相等的点集构成一个平面,法向量是a-b,过点(a+b)/2,圆O1在这个平面上向量a-b和p之间的夹角theta可以比较容易计算出来(使用内积方法和反三角函数),用球半径乘以theta的余角即可以得出所求球面距离.注意特殊情况:如果AB两点重合,则整个球面上的点到AB的距离都是相等的,那么P点到AB的距离也是相等的,所以此时所求的球面距离为P到自身的距离,为零.需要单独处理BOJ1059BalancedFood给了扇形的桌子和其上的圆形pizza的位置和大小,pizza被切成若干块(第一刀是沿x轴正向来切的),求一个取pizza的顺序,使得pizza不从桌子上掉下来如右图,左边的两块pizza先取下面的后取上面的,可以不掉下来,右边的pizza一定会掉下来扇形重心公式如果剩下的pizza的重心不在桌子上,pizza会掉下来.剩下的pizza的重心就是所有pizza片的几何中心(坐标的算术平均值),pizza片的重心可以通过积分手算出来由此可以算得每块pizza片的重心坐标,计算剩下来的这些pizza片的重心坐标的算术平均值就得到整块剩下的pizza的重心(记做C)坐标.下面的问题是判断C是否在桌子上.判断重心是否在桌上如图,tuv是桌子,c是pizza的重心坐标.注意到桌子不会比半圆更大,并且tuv是按照逆时针标号,于是得到c不在桌子上有以下情形:tu×tc<0tv×tc>0dist(t,c)>dist(t,u)ctuv实际上,还有更初等的判断方法,就是通过内积计算∠utc+∠ctv与∠utv是否相等,不等就说明c不在桌上.只是,此法需要计算反三角函数,可能会损失精度.下面的问题是,如何来取这些pizza片才能使得整块pizza不掉下去呢?吃pizza的顺序如果注意到n的大小只有10,那么可以考虑最稳妥的方法:回溯搜索.就是把所有可能的排列情况按照字典顺序都搜索一遍,找到第一个可行的顺序就退出搜索.如果搜索完成之后都没有找到可行的取法,说明没有可行方法存在.时间复杂度O(n!)具体方法,如果你曾写过求迷宫的所有可行路的程序,应该很容易实现.以上是深度优先搜索的策略实际上,本题使用贪心策略也是可以AC的(未能证明)每次都选一块编号最小的可行的pizza片,如果某一步进行不下去,就退出报告无可行取法.时间复杂度O(n2).题外话本题的操作比较复杂,使用标准C++的算法库配合复数类,可以简化操作,但是要求熟悉上述工具.BOJ1072GlobalRoaming给了卫星的极坐标,球面上一些点的极坐标,判断哪些点可以看到卫星解法甚多,以下为一种可能是比较简单的考虑地球上一点的切平面,它的法向量从地心指向该点.下面只需要判断卫星位于切平面的那一侧即可,这是我们已经解决的问题.初等数论初等数论的内容也是比较多的,本次主要介绍素数的测试,数的整除性和跟同余有关的一些知识.素数测试这是数论里的一个基本问题,而且现代社会应用也很广泛,发展了很多算法.首先要知道下面的方法.给了一个数n,从i＝3开始到n的算术根以步长2进行循环，如果n都不能整除i，那么n就是一个素数这种方法效率比较低,判断一个数需要O(n1/2)的时间复杂度Eratosthenes筛法筛法(续)筛法并不仅用于计算素数,它还用于很多其它类似机理的场合(如BOJ1074AssistanceRequired)例如,计算Euler函数时,可以利用筛法来标号概率型算法注意到上述两种方法其实都是比较慢的,为了快速判断是否素数,出现了多种测试素数的方法Miller-Rabin测试:基于Fermat小定理的测试,一次测试把一个合数判断成素数的概率小于1/4,多次测试使得犯错误的概率更小.参加ACM竞赛需要知道这个算法,具体细节可在网上找到唯一分解定理每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现,换句话说,任意正整数n可以写成n=2a1*3a2*5a3*…,其中a1,a2,a3等为非负整数,这称为n的素因子标准分解式数的整除性令a和b是不全为0的两个整数，能使d|a和d|b的最大整数称为a和b的最大公约数，用gcd(a,b)表示，或者记为(a,b)令a和b是不全为0的两个整数，能使a|d和b|d的最小整数称为a和b的最小公倍数，用lcm(a,b)表示，或者记为[a,b]定理:ab=gcd(a,b)*lcm(a,b)GCD的计算计算gcd(m,n),使用Euclid除法:while(m>n?(m%=n):(n%=m));GCD为m,n中的非零数,也可以写为m+n.时间复杂度O(logn),若m>n上面为循环算法,可以写出递归算法.GCD的计算(2)如果(a,b)=d,则一定存在整数x,y,使得xa+yb=d.求x,y,仍然使用(扩展的)Euclid算法(递归实现):int

gcd(inta,intb,int&x,int&y){

if(!b){x=1;y=0;returna;}else{intr=gcd(b,a%b,x,y);t=x;x=y;y=t–a/b*y;returnr;}}同余设m是一个正整数,若a,b是整数,且m|(a-b),则称a和b模m同余,记做a≡b(modm)整数的一种分类方法:给了一个整数m,则可以把整数按照除m的余数分为m类.特别地,m=2时,分为奇数和偶数同余性质设m是正整数,则下面命题成立:(i)b1≡a1(modm),b2≡a2(modm),则:b1±b2≡a1±a2(modm),b1b2≡a1a2(modm)若ac≡bd(modm),c≡d(modm),且(m,c)=1,则a≡b(modm)Euler函数定义:1~n中和n互素的正整数个数记做

(n),

即为Euler函数

Euler函数的性质:(mn)=(m)(n),m,n是互素正整数.设正整数 为n的素因子标准分解式,则:上述两条性质可以用于计算Euler函数的数值涉及计算Euler函数值的ACM赛题,可以参见POJ2480Longge'sproblem,POJ2478FareySequenceEuler定理设k是与正整数m互素的整数,则k(m)≡1(modm)推论(Fermat小定理):设p是素数,若p不能整除k,则kp-1≡1(modp)中国剩余定理(孙子定理)设m1,m2,…,mk是k个两两互素的正整数,任给k个整数a1,a2,…,ak,必存在整数x,使得x≡ai(modmi)(i=1,2,…,k),且在0<=x<M=m1m2…mk内有唯一解从此定理的证明过程我们可以得到求出x具体算法记Mi=M/mi，则(Mi,mi)=1存在pi,qi，Mipi+miqi=1记录ei=Mipi，则j=i时ei≡1(modmj)J≠i时ei≡0(modmj)则e1a1+e2a2+…+ekak就是一个解,调整(加减M)得到[0,m)内的唯一解.此算法用到先前的(扩展的)Euclid除法此问题的一个实例可以参看POJ1006BiorhythmsBOJ1040Goldbach's

Conjecture

给了偶数n,求两个素数a,b,使得n=a+b,并且b-a的值最大.使用筛法选出一个到1000000的素数表,然后从i=3开始枚举素数,遇到合适的就停下来BOJ1074AssistanceRequired也是筛法的例子,把2的倍数筛掉,再把3的倍数筛掉,…,求剩下来的数中的第n个.在筛的过程中,把没有筛掉的放到一个数组中,可以直接输出第n个数.BOJ1008Happy20042004x的所有因数的和,除以29的余数是多少?首先,根据Fermat小定理,200428≡1(mod29),根据同余性质,200428n≡1(mod29).又知(a+b)%c=(a%c+b%c)%c,(ab)%c=(a%c)(b%c)%c简化计算的因子考虑2004x的因子,把它们分成以下几类:是2004x-28n的因子,当然也是2004x的因子不是2004x-28n的因子,但是2004x的因子首先说明,第二类因子的和模29等于0.2004=22*3*167,根据同余性质,只需要考虑4,3,22(=167%29)作为2004的因子.令y=x-28n,则第二类因子必然可以写为ay*2s*3r*22t的形式,其中a=22,3,22证明细节在上述表达式中,2s*3r*22t一定是200428n的因子.从而,s,r,t一定可以取遍1~28n(s到56n)的值.固定r,t的取值,对s求和,只需证明∑say*2s*3r*22t%29=0,其中y,r,t是常数.上式等价于证明∑s2s%29=0,s=1,…,56n,由等比数列求和公式得到∑s2s=256n-1.另一方面,根据Fermat小定理,228≡1(mod29),从而256n-1%29=0,得证.求解我们只需要考虑2004y的因子的和模29.其中y=x%28.2004y的素因子标准分解式为22y3y167y,只需考虑形如22s*3r*22t(s,r,t<=y<28)的因子.可以通过枚举法得出所有因子.进一步,这些因子的和模29的结果就可以得出来了

优化建议不用考虑所有因子,只分别考虑4,3,22的幂这部分因子的和模29的结果,相乘后再模29可得最后结果.依据:求余操作可以与加法和乘法交换次序.基于上面的结果,注意到这些幂的指数最大到27,可以做三个表,分别存放4,3,22的幂的和模29的结果.如p4[i]表示∑0<=s<=i4s%29的结果.如此,只要知道了y,最后的结果为(p4[y]*p3[y]*p22[y])%29组合数学组合数学的内容很多,题目也可以出到很困难,只介绍最基础的跟本次题目相关的内容.排列数和组合数组合数的计算组合数由于阶乘的数量级很大,所以通常在计算时都采用边乘边除的方法,以避免溢出.更强的优化方法是在乘之前先把分子的所有数与分母约分,这样,如果能保证最后不溢出,那么中间步骤也一定不会溢出圆排列(循环排列)定理:n个元素的集合的循环r排列的个数为多重集的排列定理1:令S是一个多重集,它有k个不同类型的元素,每一个元素都有无穷重复个数.则S的r排列的个数是kr定理2:令S是一个多重集,有k个不同类型的元素,个元素的重述分别为n1,n2,…,nk.设S的大小为n=n1+n2+…+nk,

则S的排列数等于多重集的组合定理:令S为具有k种类型元素的一个多重集,每种元素均有无穷重复数,则S的r组合的个数等于当元素的重复数不是无穷时,计算这样的r组合需要使用生成函数(母函数),容斥原理等工具.组合数学的大致内容对于要参加ACM竞赛的同学,最好要掌握下面的一些知识(主要是用于计数):排列组合原理(包括禁位排列等非常规情形)容斥原理生成函数和递推关系一些特殊的计数序列,例如Catalan数(如BOJ1007就是计算这个数)Polya计数法(复杂的计数,如BOJ1051)此外,ACM竞赛中还可能考离散概率论,主要也是结合组合计数来考的.概率论的古典概型(不一定是离散的)也可能会出现在ACM赛场上(如POJ2598MatchThrowingGame,蒲丰投针问题)BOJ1064PathsonaGrid为多重集的排列问题,归结为计算组合数BOJ1027BinomialShowdown,计算组合数BOJ1085InDanger经典的Josephus问题:n个人围成一圈从1到n编号,从第一个人开始进行一二报数,报到二的出队,问最后留下来的是哪一个人.这个问题的一般形式是报数从1到m报数,但是当m=2时(也就是本题的情形),可以推出形式比较简单的公式.推导过程我们可以从数字比较小的情况开始来猜测公式的形式,然后使用数学归纳法来证明.我们记J(n)为n个人时的最后剩下来的编号,显然,J(1)=1