第二讲-乘方取模和矩阵快速幂.ppt

第二讲 乘方取模和矩阵快速幂 詹海艳 一 乘方取模问题 二分思想 n为偶数 m n为奇数 注 把时间复杂度从O n 降为O logn 了 快速幂取余 m n k模板intquickpow intm intn intk intb 1 while n 0 if n 例题 HDOJ1061 ProblemDescriptionGivenapositiveintegerN youshouldoutputthemostrightdigitofN N InputTheinputcontainsseveraltestcases ThefirstlineoftheinputisasingleintegerTwhichisthenumberoftestcases Ttestcasesfollow EachtestcasecontainsasinglepositiveintegerN 1 N 1 000 000 000 OutputForeachtestcase youshouldoutputtherightmostdigitofN N SampleInput234SampleOutput76 解答 include include include include include include includeusingnamespacestd defineMA10010intPowerMod inta intb intc intans 1 a a c while b 0 if b returnans intmain intn t s scanf d 二 矩阵快速幂 定义 引入 若A是一个矩阵 那么求A的n次方的过程就是矩阵快速幂 举个例子 求第n个Fibonacci数模M的值 如果这个n非常大的话 普通的递推时间复杂度为O n 这样的复杂度很有可能会挂掉 这里可以用矩阵做优化 复杂度可以降到O logn 2 3 如图A F n 1 B F n 2 这样使构造矩阵的n次幂乘以初始矩阵得到的结果就是 因为是2 2的据称 所以一次相乘的时间复杂度是O 2 3 总的复杂度是O logn 2 3 2 2 1 矩阵快速幂与斐波那契数列的关系 其实用的更多是使用矩阵快速幂 算递推式 注意是递推式 简单的如斐波那契数列的第一亿项的结果模10000000后是多少你还能用递推式去 逐项递推吗 当然不能 这里就可以发挥矩阵快速幂的神威了 那斐波那契数列和矩阵快速幂能有一毛钱的关系 答案是有而且很大斐波那契的定义是f 1 f 2 1 然后f n f n 1 f n 2 n 2 我们也可以这样定义f 1 f 2 1 f n f n 1 f n 1 f n 2 1 1 1 0 其中 1 1 1 0 是一个2 2的矩阵上面一行是1 1 下面一行是1 0 这样就可以化简了写成 f n f n 1 f 2 f 1 1 1 1 0 n 2 简单描述 f n f n 1 f n 1 f n 2 X这样就可以用矩阵快速幂 快速的推出斐波那契数列的第一亿项的值了 当然是取模的值了 是不是很神奇 类似的递推式也可以 化成这种形式 用矩阵快速幂进行计算 矩阵快速幂模板 include include include includeusingnamespacestd constlonglongM 1000007 constlonglongN 3 longlongt b c f1 f2 structNode 矩阵 longlongline cal longlonga N 1 N 1 Node line 3 cal 3 a 0 0 b a 0 1 1 a 0 2 0 a 1 0 t a 1 1 0 a 1 2 0 a 2 0 c a 2 1 0 a 2 2 1 Nodeisit Nodex longlongc 矩阵初始化 for longlongi 0 i N i for longlongj 0 j N j x a i j c returnx NodeMatlab Nodex Nodes 矩阵乘法 Nodeans ans line x line ans cal s cal ans isit ans 0 for longlongi 0 i x line i for longlongj 0 j x cal j for longlongk 0 k s cal k ans a i j x a i k s a k j ans a i j ans a i j M M returnans longlongFast Matrax longlongn 矩阵快速幂 if n 1 returnf1 n 2 longlongx 1 f n ok 1 Nodeans tmp ch ans line 1 ans cal 3 ans a 0 0 f2 ans a 0 1 f1 ans a 0 2 1 while n 0 if n 2 ans Matlab ans tmp tmp Matlab tmp tmp n 2 returnans a 0 0 intmain longlongn T scanf lld 例题 HDOJ1005 Anumbersequenceisdefinedasfollows f 1 1 f 2 1 f n A f n 1 B f n 2 mod7 GivenA B andn youaretocalculatethevalueoff n InputTheinputconsistsofmultipletestcases Eachtestcasecontains3integersA Bandnonasingleline 1 A B 1000 1 n 100 000 000 Threezerossignaltheendofinputandthistestcaseisnottobeprocessed OutputForeachtestcase printthevalueoff n onasingleline SampleInput1131210000SampleOutput25 解答 公式法 include includeintmain inta b n i while scanf d d d 解答 矩阵快速幂法 include include include include include defineinf0 x3f3f3fusingnamespacestd structmat intmatrix 2 2 typedefstructmatMatrix Matrixmul Matrixa Matrixb Matrixresult result matrix 0 0 a matrix 0 0 b matrix 0 0 a matrix 0 1 b matrix 1 0 7 result matrix 0 1 a matrix 0 0 b matrix 0 1 a matrix 0 1 b matrix 1 1 7 result matrix 1 0 a matrix 1 0 b matrix 0 0 a matrix 1 1 b matrix 1 0 7 result matrix 1 1 a matrix 1 0 b matrix 0 1 a matrix 1 1 b matrix 1 1 7 returnresult voidqsm intp intq intn Matrixc d c matrix