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

《acm程序设计竞赛 数学基础 刘汝佳》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数学基础(版本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下同构1212121234343434分析•先把置换它分解成为循环,首先证明长度为L的偶循环将导致无解–对于

2、点i,记P(i)=i,假设i和i的边方向为1kk+11L/2+1i->i,那么有i->i,i->i,…,i->i,1L/2+12L/2+23L/2+3L/2+11和假设矛盾!•假设确定其中k条独立边后其他边也会确定,则答案为2k•考虑两类边:循环内边和循环间边.分析•循环内顶点的关系–定了i和i之间的关系,i与i之间的关1jk(k+j-2)modn+1系也被确定下来了,因此只需要确定i和i,i,…,123i这(L-1)/2对顶点的关系(L-1)/2+1•不同循环间顶点的关系–设循环为(i,i,…,i)和(j,j,…,j),通过类似分12L112L2析得只需要确定gcd(L1,L2)对关系即

3、可分析•最后答案为2k1+k2•其中k1=sum{(L-1)/2},k2=sum{gcd(L1,L2)}•可以用二分法加速求幂例2.图形变换•平面上有n个点需要依次进行m个变换处理•规则有4种,分别把(x,y)变为00–平移M(x,y):(x+x,y+y)00–缩放Z(L):(Lx,Ly)00–翻转F(0):(x,-y);F(1):(-x,y)0000–旋转R(a):a为正时逆时针,离原点距离不变,旋转a度•给n(<=106)个点和m(<=106)条指令•求所有指令完成后每个点的坐标分析•如果直接模拟,每次需要O(n)的时间,一共O(nm),无法承受•把点(x,y)写成列向量[x,y]T,

4、则后3种变0000换可以都可以写成矩阵–缩放P’=Z*P,Z=[L0;0L]–翻转P’=F*P,F=[10;0-1]或[-10;01]–旋转P’=R*P,R=[cosa–sina;sinacosa]•可是无法实现平移,怎么办呢?分析•修改表达方式,令P=[x,y,1]T,则四种变00换的矩阵M,Z,F,R分别为⎡10xL⎤⎡⎤00⎡⎤100⎡⎤−100My==⎢01⎥⎢⎥,Z0L0⎢⎥⎢⎥⎢⎥⎢⎥F=−⎢⎥010010或⎢⎥⎢⎣001⎥⎢⎥⎦⎣⎦001⎢⎥⎣⎦001⎢⎥⎣⎦001⎡cosaa−sin0⎤⎢⎥,sRaa=incos0⎢⎥⎢⎣001⎥⎦分析•只需要先计算所有变换矩阵的乘积A,然

5、后对于每个点,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)=su

6、m{SK-1(i,x)*S(x,j)},乘法原理•因此Sn的所有的元素之和就是答案例4.硬币•给定长度为K-1的二进制数组A，对K个排放好的硬币序列C，在其上定义X操作：–将C向左循环移动一格–如果第i（1≤i

7、建立若干方程，求解出A数组，这是很容易做到的。•接下来要逆推求出原先的硬币状态，如果用基本的模拟，时间复杂度势必非常高。•对于长度为K的硬币序列C的多次操作（逆操作可类似求解）,有两种方法方法一•设G[i]表示C..C,C..C这个硬币序列，经i+1k1i过一次X操作，是否会导致C变化i•设q[i][x]代表如果C变化，那么G[x]是否会i发生变化，q数组可以预先处理,并对其进行位压缩再使用xor进行模拟，降低常数项•时