umm首先矩阵快速幂的板子就不港了比较简单的还是?就结合二进制地理解一下就好了,代码可以翻蒟蒻の考前续命这里面放了我记得?
主要是说下应用趴?
目前我会的似乎就是个矩阵加速?简单来说就是个给一个递推式(以板子为例说下?那么递推式就是f[x]=f[x-3]+f[x-1])给一个k要快速地求出f(k)
umm其实这个的话就是构造一个矩阵,然后套个矩阵快速幂就好了鸭
矩乘当然是板子的了,主要问题在于构造矩阵,这里港下我肝了一个下午的理解qwq
定义
首先我们要理解矩阵?它的作用在哪儿?
umm这个点的话我觉得结合方程组和图像应该会好理解一些?然而我懒得画图也懒得举例辽QAQ所以放一个我学习矩阵的网址这里我觉得解释得真的贼好QwQ特别便于理解QwQ
矩阵加速线性递推式
然后矩阵最重要的应用应该就是矩阵加速?然后矩阵加速唯一一个有难度的就在于怎么构造矩阵
那就以f[i]=f[i-1]+f[i-3]为例港下
很容易能发现我们是从f[n-1],f[n-2],f[n-3]推出f[n],f[n-1],f[n-2],那我们就可以做出这样一个东西
f[n-1] f[n]
f[n-2] × T = f[n-1]
f[n-3] f[n-2]
然后!如果我们能求出T,就可以矩阵快速幂地求出来辣!
然后思考一下可以得到f[]之间的关系
f[ n ]=1*f[n-1]+0*f[n-2]+1*f[n-3]
f[n-1]=1*f[n-1]+0*f[n-2]+0*f[n-3]
f[n-2]=0*f[n-1]+1*f[n-2]+0*f[n-3]
就能构造出
1,0,1
1,0,0
0,1,0然后快速幂走一波,over
然后还有一个小细节是关于最开始的那个矩阵?
那个我不会构造,,,,所以我一直是大概性地猜一把然后多套几个数据然后就大概套出来了,,,关于这个我还没有总结出来呢QAQ等多打几个模板再总结下趴QAQ
然后之前考试的时候碰到了类似的题目,tr神仙总结了一下QwQ
首先我们要知道,对于矩阵来说,尽量是越小越好的
举个eg,2×2的矩阵,和3×3的矩阵,相差就会有3倍的常数
所以矩阵能小尽量小
然后关于上面那个T的最小size,先写个一般式:f[i]=A*f[i-1]+B*f[i-2]+C
首先想到因为矩阵乘法都是乘法,肯定搞不出加法的,所以状态要设成这样:
f[i-1] f[i]
f[i-2] × T = f[i-1]
C C
然后就看
f[i]=A*f[i-1]+B*f[i-2]+1*C
f[i-1]=1*f[i-1]+0*f[i-2]+0*C
C=0*f[i-1]+0*f[i-2]+1*C
所以构出来就是这样儿的
A,B,1
1,0,0
0,0,1
然后如果再一般一点儿,变成这样呢:f[i]=A*f[i-d1]+B*f[i-d2]+C
也是能解决的,懒得画图辣,写一个结论
f[i]=A1*f[i-1]+A2*f[i-2]+A3*f[i-3]+...
构造出来的T就是
A1,A2,A3, ...
1 , 0, 0, ...
0 , 1, 0, ...
...
然后如果还有个常数就另外加个常数就欧克,看上面"f[i]=A*f[i-1]+B*f[i-2]+C"这个的应该就欧克辣
以上就是,矩阵快速幂优化线性递推式的方法
就是矩阵加速的最基础应用,,,
矩阵光速幂
瞎取的名字,,,不知道484叫这个玩意儿,,,
还麻油落实,,,
放个例题:块速递推
拓展1 矩阵套矩阵
咕咕咕,,,?
拓展2 经典递推式
有好几个加法乘法的经典式子
如果明天能逃过来就写QAQ
然后最后放几个基本的题目就溜辣!
[X] 斐波那契数列