ACM中矩阵应用.ppt

矩阵及其应用 雍高鹏 矩阵乘法及其优化 对于整形数字b=a^k%m，当k很大的时候（1e9），可以用二分的思想快速求出b的值。 快速幂 那么，类似的，对于矩阵s，s^k%mod也可以快速求出。 复杂度分析，在算法竞赛中，矩阵的规模不会太大，乘法的O(N^3)当做常数处理。 S^k可以用二分求解，如果是S^1+S^2+….+S^k呢？答案就是，二分，再二分。 快速幂 上面mat_plu()是矩阵相加的函数，对应位置相加。 以k=16为例： s^1+…s^16=(s^1+…+s^8)+s^8(s^1+…+s^8) s^1+…+s^8=(s^1+…+s^4)+s^4(s^1+…+s^4) … 规模依次折半。 给定n个点，对所有点同时进行m个操作（操作包括平移、缩放、翻转和旋转），试构造O(m+n)的算法输出m个操作后各点的位置。 其中翻转是以坐标轴为对称轴进行翻转（两种情况），旋转则以原点为中心。 关于构造 求第n个Fibonacci数mod p的值。 Fibonacci数的递推关系，f(n)=f(n-1)+f(n-2)。我们就要试图找到一个矩阵 s，使得 s与(a,b)（a、b为两个连续Fibonacci数）相乘后，会得到(b,a+b)这种形式。因此矩阵可以构造为 更一般的：找到 f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项 其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。 关于构造 一张N个点的无向无权图。如果点a和点b之间有边，那么邻接矩阵 G[a][b] = G[b][ a] = 1，否则等于0。 那么，考虑邻接矩阵自乘，即G^2，会有什么意义。 若G^2[a][b]！=0，就说明存在点i，使得a i 间有边并且i b 间也有边。G^2[a][b]的值，即为从点a到点b经过1个中间点的路径条数。 对于G^3,即G[a][ i]G[i][ j]G[j][ b] = 1当且仅当G[a][i] = G[i][ j] = G[j][ b] =1，也就是说a-i-j-b组成一条路经。那么G^3[a][ b]的值就是从点a到点b经过2个中间点的路径条数。 因此，运用数学归纳法不难证明， G^k[a][ b]就等于a到b经过k-1个中间点也就是长度为k的路径条数。 图的邻接矩阵的应用 一些推广及处理： 1、前面的结论同样适用于有向图。 2、对于有重边的图，只需要把G[a][ b]改为表示点a, b之间重边的数目。 3、对于有向图的自环，直接加边即可。 4、对于无向图的自环，通常是把G[a][a]加上2，这样在计算G^k的时候这条边就被算成2条不同的边，如果只加上1，又会不满足矩阵里所有元素和等于边数两倍的性质(入度和出度)。 5、忽略前面所说的，具体问题具体分析。 图的邻接矩阵的应用 给定一张M条边的无向带权图，求从起点S到终点E恰好经过K条边的最短路径。2=M=100,2=K=1000000。 思考：考虑无向无权图，经过k条边是通过k次矩阵的相乘得到的，结果得到的是路径数。因为矩阵相乘的实质是固定两端、枚举中间节点，计算结果全部加和。g[i] [j] = ∑ g[i] [k]*G[k][ j] 现在要求的是最短路. f[i] [j] =min(f[i][k] + G[k][ j]) 从方程的比对中，可以发现我们只需重定义矩阵乘法。每经过一条路做一次floyd即可。 图的邻接矩阵的应用 有K种珍珠，每种N颗，求这些珍珠组成的长度在1~N之间包含K种珍珠的项链有多少种（答案模1234567891）。 其中，1=K=30,1=N=1000,000,000 状态转移方程：?dp[i][j] = j*dp[i-1][j]+(k-j+1)*dp[i-1][j-1].其中 dp[i][j]表示包含j种珍珠且长度为i的项链的种数。ans= dp[1][k]+…+dp[n][k] 直接开dp[][]数组会MLE，用滚动数组O(nk)递推会TLE. 注意到，dp[i][]的状态只与dp[i-1][]相关，那么从状态dp[i-1][]转移到状态dp[i][]，相当于一个k*k的线性变化。即F[i]=A*F[i-1]，这里A是转移矩阵，即F[i]=Ai-1*F[1]，所以ans=F[1]+…+F[n]=A0*F[1]+…+An-1*F[1]=(E+A+A2+…+An-1)*F[1]。 (注意这里有矩阵，自己构造自己想) 优化DP 使用矩阵优化的条件： 1、状态必须是一维或者两维，如果状态本身有超过两维要状态压缩。 2、每一个状态dp[i] []必须满足