acm程序设计竞赛 数学基础 刘汝佳

数学基础(版本2009)刘汝佳Mathworld.wolfram.com例1.同构计数•一个竞赛图是这样的有向图–任两个不同的点u、v之间有且只有一条边–不存在自环•用P表示对竞赛图顶点的一个置换。当任两个不同顶点u、v间直接相连的边的方向与顶点P(u)、P(v)间的一样时，称该图在置换P下同构•对给定的置换P，我们想知道对多少种竞赛图在置换P下同构例1.同构计数•例：有顶点1、2、3、4和置换P：P(1)=2，P(2)=4，P(3)=3，P(4)=1•对于下图的四种竞赛图，在置换P下同构1324132413241324分析•先把置换它分解成为循环,首先证明长度为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)modn+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=sum{gcd(L1,L2)}•可以用二分法加速求幂例2.图形变换•平面上有n个点需要依次进行m个变换处理•规则有4种,分别把(x0,y0)变为–平移M(x,y):(x0+x,y0+y)–缩放Z(L):(Lx0,Ly0)–翻转F(0):(x0,-y0);F(1):(-x0,y0)–旋转R(a):a为正时逆时针,离原点距离不变,旋转a度•给n(=106)个点和m(=106)条指令•求所有指令完成后每个点的坐标分析•如果直接模拟,每次需要O(n)的时间,一共O(nm),无法承受•把点(x0,y0)写成列向量[x0,y0]T,则后3种变换可以都可以写成矩阵–缩放P’=Z*P,Z=[L0;0L]–翻转P’=F*P,F=[10;0-1]或[-10;01]–旋转P’=R*P,R=[cosa–sina;sinacosa]•可是无法实现平移,怎么办呢?分析•修改表达方式,令P=[x0,y0,1]T,则四种变换的矩阵M,Z,F,R分别为100001,00001001xLMyZL⎡⎤⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦100100010010001001F−⎡⎤⎡⎤⎢⎥⎢⎥=−⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦或cossin0,sincos0001aaRaa−⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦分析•只需要先计算所有变换矩阵的乘积A,然后对于每个点,P’=A*P•注意:矩阵乘法不满足交换律,因此需要按照输入顺序进行乘法•每次矩阵乘法需要33=27次乘法,则计算A一共需要27m次乘法,对所有点变换需要27n次乘法,一共27(n+m)次例3.染色方案•N*M(N=10100,M=5)的格子纸，每个格子被填上黑色或者白色。求没有任何一个2*2的格子同色的染色方案总数modP。分析•每行最多32(=2M)种状态•任两种状态是否可组成相邻行，可以用一个32*32的矩阵S表示•下面证明Sk的元素(i,j)表示以i为第一层,j为最后一层,共k+1层的方法数•K=0时显然成立,考虑Sk=Sk-1*S,任何一个元素SK(i,j)=sum{SK-1(i,x)*S(x,j)},乘法原理•因此Sn的所有的元素之和就是答案例4.硬币•给定长度为K-1的二进制数组A，对K个排放好的硬币序列C，在其上定义X操作：–将C向左循环移动一格–如果第i（1≤iK）个硬币背面朝上，并且Ai=1，那么将第K个硬币翻面。•给定L组，K个硬币的样板X操作情况（初始状态和X操作后的状态），保证它们可以唯一地得到A，并且一定能得到A。•另外有一个长度为N的硬币序列，在其上进行M组操作，每组操作对Si~Si+K的硬币进行Di次X操作。给定这组硬币最终状态，求其初始状态。分析•考虑直接套用给定的X操作样板，但简单试验后不难发现这是不可能的。•根据样板，建立若干方程，求解出A数组，这是很容易做到的。•接下来要逆推求出原先的硬币状态，如果用基本的模拟，时间复杂度势必非常高。•对于长度为K的硬币序列C的多次操作（逆操作可类似求解）,有两种方法方法一•设G[i]表示Ci+1..Ck,C1..Ci这个硬币序列，经过一次X操作，是否会导致Ci变化•设q[i][x]代表如果Ci变化，那么G[x]是否会发生变化，q数组可以预先处理,并对其进行位压缩再使用xor进行模拟，降低常数项•时间O(L3+MD),空间O(NL+N)方法二•根据A，可以用固定的矩阵B表示X操作。那么C*BDi表示对硬币序列的Di次x操作，而矩阵B的Di次方可以用logi次乘法完成•时间O(L3+MK3logD),空间O(NL+N2logD)例5.XOR电路•输入用长度为n的01串表示。给出A和B，统计A~B中有多少个串让输出为1分析•使输出为1的输入满足模线性方程•对于给定的上限upper和下限lower，我们可以分别求出在下限是00…0的情况下上限是upper的解数u和上限是lower的解数l。若lower是一组满足条件的解，则总的解数为u-l+1，否则最终的解数是u-l•问题的关键：计算上限upper和下限00…0时解的个数分析•方程只有1个而变量有多个，设变量个数为m，则可以有m-1个数任意取值，因为最后一个数一定有办法使方程成立•设编号最大的输入代表的变量为最后一个变量（设为k），则除k以外的其他输入可以任意取值，而k的取值受到限制例6.灯泡•有n(=106)个灯排列成环形.每个单位时间,灯i改变状态当且仅当上一个时刻它下一个灯(in时为i+1,i=n时为1)开着.•给n个灯的初始状态以及m(m=109),给出m时间单位以后的状态.分析•算法一:直接模拟O(nm)•算法二:事先计算循环节,则时间复杂度和m无关,上限是O(n2n),但具体运行时间不好估计•算法三:第一次a1,i=a0,ixora0,i+1,第二次a2,i=a1,ixora1,i+1=(a0,ixora0,i+1)or(a0,i+1ora0,i+2)=a0,ixora0,i+2,第四次a4,i=a2,ixora2,i+2=(a0,ixora0,i+2)xor(a0,i+2xora0,i+4)=a0,ixora0,i+4•至此,规律已经很明显.二分法即可.O(nlogm)例7.水桶•桶里注入密度为1的水,然后放入大小不一的立方体,最后盖一个盖子并压紧.•给出桶底面积S,高H,水的体积V(V=S*H),以及n个立方体的边长和密度,求最后的水位高度和素数有关的问题•如何求1~n的所有素数?•如何判断一个数n是否为素数?•如何求两个数的最大公约数?•如何给一个数n分解素因数?问题1:1~n的素数•假设要求1~100的素数–2是素数,删除2*2,2*3,2*4,…,2*50–第一个没被删除的是3,删除3*3,3*4,3*5,…,3*33–第一个没被删除的是5,删除5*5,5*6,…5*20•得到素数p时,需要删除p*p,p*(p+1),…p*[n/p],运算量为[n/p]-p,其中p不超过n1/2(想一想,为什么)Eratosthenes的筛子小知识：各种筛法小知识:素数的个数•近似公式(Legendre常数B=-1.08366)问题2:素数判定•枚举法:O(n1/2),指数级别•改进的枚举法:O(phi(n1/2))=O(n1/2/logn),仍然是指数级别•概率算法:Miller-Rabin测试+Lucas-Lehmer测试Miller-Rabin测试•对于奇数n,记n=2r*s+1,其中s为奇数•随机选a(1=a=n-1),n通过测试的条件是–as≡1(modn),或者–存在0=j=r-1使得a2^j*s≡-1(modn)•素数对于所有a通过测试,合数通过测试的概率不超过1/4•只测试a=2,3,5,7,则2.5*1013以内唯一一个可以通过所有测试的数为3215031751思考：区间内的素数•给出n,m(n=106,m=105),求n~n+m之间的素数有多少个•哪种方法快?筛还是依次素数判定?小知识：PRIMESisinP•三个印度人M.Agrawal,N.Kayal和N.Saxena与2002年证明了PRIMES可以在多项式时间内完成关于AKS算法•Commentingontheimpactofthisdiscovery,P.Leylandnoted,Onereasonfortheexcitementwithinthemathematicalcommunityisnotonlydoesthisalgorithmsettlealong-standingproblem,italsodoessoinabrilliantlysimplemanner.Everyoneisnowwonderingwhatelsehasbeensimilarlyoverlooked(quotedbyCrandallandPapadopoulos2003).问题3:最大公约数•方法一:使用惟一分解定理,先分解素因数,然后求最大公约数•方法二:(Euclid算法)利用公式gcd(a,b)=gcd(b,amodb),时间复杂度为O(logb)•方法三:(二进制算法)若a=b,gcd(a,b)=a,否则–A和b均为偶数,gcd(a,b)=2*gcd(a/2,b/2)–A为偶数,b为奇数,gcd(a,b)=gcd(a/2,b)–如果a和b均为奇数,gcd(a,b)=gcd(a-b,b)•不需要除法,适合大整数扩展问题•一定存在整数x,y，使得ax+by=gcd(a,b)intgcd(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;}}•由数学归纳法可证明ax+by=gcd(a,b)•满足ax+by=d的数对(x,y)不是惟一的,因为当x增加b且y减少a时和不变。问题4:分解因数•分解因数可以转换为求最小素因子(找到最小素因子后递归求解)•分解素因数后得到惟一分解式sum{piki},可以求出约数个数,即所有ki+1的乘积(由乘法原理容易证明)•方法一:试除法•方法二:pollard-rho算法小知识：因数分解算法RSA加密小知识：历史上的RSA例1.破解RSA•给定M个数，它们的质因子在前T个质数范围内。选出至少一个数,使得它们的积为完全平方数.求方案总数分析•首先将读入的M个数，分解质因数，并对每个质因数出现次数的奇偶性进行记录。•设x[i]=0或1代表是否使用第i个数。可以列出一个关于x[i](1=i=m)的位方程组（乘积的所有质因数出现次数均为偶数）。•解该方程组，检查最后有多少自变量，设有n个，那么结果应该是2n-1（除去空集）。时空复杂度均为O(M2)例题2.奇怪的计数器•用如下方式表示数：•AN-1*2N-1+AN-2*2N-2+...+A1×2+A0•每个A在范围0~2内。•初始时所有的A均为0，要处理M次加2x的操作（每个x不一定都相同），每次最多只允许修改4个A的内容。•要求模拟这一过程。分析•多个2连在一起比较“危险”，容易超过4次的限额•让它们之间存在一个0，就缓解了压力•考虑这样的限制条件–任意两个相邻的2之间至少有一个0–从最低一位2向更低的位数找，也至少能找到一个0•限制条件避免了一次操作需要影响O(N)个二进制位的退化情况，类似于在排序二叉树中加入了“平衡因子”这个限制。因此不妨称这个限制条件为“平衡性质”。分析•一开始的0序列满足平衡性质，因此需要构造从一个平衡状