矩阵加速入门2
思路：
基础的矩阵快速幂题，稍微卡常。
原始矩阵：
\(\begin{bmatrix} f_2 & f_1 \end{bmatrix}\)
加速矩阵：
\(\begin{bmatrix} 1&1 \\ 1&0 \end{bmatrix}\)
代码：
Code
L.n=1,L.m=2;
R.n=R.m=2;
L.Mat[1][1]=1;L.Mat[1][2]=1;
R.Mat[1][1]=1;R.Mat[1][2]=1;
R.Mat[2][1]=1;R.Mat[2][2]=0;
Matrix ans=L*QuickPow(R,n-2);
printf("%lld\n",ans.Mat[1][1]);
矩阵加速入门3
思路：
题目在 \(f_{n-1}\) 与 \(f_{n-2}\) 前分别加上了一个常数，只需把加速矩阵中的常数 \(1,1\) 变为 \(p,q\) 即可。
原始矩阵：
\(\begin{bmatrix} f_2 & f_1 \end{bmatrix}\)
加速矩阵：
\(\begin{bmatrix} p&1 \\ q&0 \end{bmatrix}\)
代码：
Code
L.n=1,L.m=2;
R.n=R.m=2;
L.Mat[1][1]=1;L.Mat[1][2]=1;
R.Mat[1][1]=p;R.Mat[1][2]=1;
R.Mat[2][1]=q;R.Mat[2][2]=0;
Matrix ans=L*QuickPow(R,n-2);
printf("%lld\n",ans.Mat[1][1]);
矩阵加速入门4
思路：
此题为3题的变式，很容易想到将 \(2*2\) 的矩阵变为 \(5*5\) 的矩阵，只是注意快速幂的幂应减去 \(5\)。
原始矩阵：
\(\begin{bmatrix} f_5 &f_4 &f_3 &f_2 & f_1 \end{bmatrix}\)
加速矩阵：
\(\begin{bmatrix} p&1&0&0&0 \\ 0&0&1&0&0 \\ 0&0&0&1&0\\0&0&0&0&1\\q&0&0&0&0\end{bmatrix}\)
代码：
Code
L.n=1,L.m=5;
R.n=R.m=5;
L.Mat[1][1]=1;L.Mat[1][2]=1;L.Mat[1][3]=1;L.Mat[1][4]=1;L.Mat[1][5]=1;
R.Mat[1][1]=p;R.Mat[1][2]=1;R.Mat[1][3]=0;R.Mat[1][4]=0;R.Mat[1][5]=0;
R.Mat[2][1]=0;R.Mat[2][2]=0;R.Mat[2][3]=1;R.Mat[2][4]=0;R.Mat[2][5]=0;
R.Mat[3][1]=0;R.Mat[3][2]=0;R.Mat[3][3]=0;R.Mat[3][4]=1;R.Mat[3][5]=0;
R.Mat[4][1]=0;R.Mat[4][2]=0;R.Mat[4][3]=0;R.Mat[4][4]=0;R.Mat[4][5]=1;
R.Mat[5][1]=q;R.Mat[5][2]=0;R.Mat[5][3]=0;R.Mat[5][4]=0;R.Mat[5][5]=0;
Matrix ans=L*QuickPow(R,n-5);
printf("%lld\n",ans.Mat[1][1]);
矩阵加速入门5
思路：
此题与 \(3\) 题只相差一个 \(n\)，考虑如何构造 \(n\)。我的想法是将原始矩阵带入 \(n\) 与 \(1\) ，在每次相乘时都加上一个自身与 \(1\) 即可。
原始矩阵：
\(\begin{bmatrix} &f_2 & f_1 & 2 & 1 \end{bmatrix}\)
加速矩阵：
\(\begin{bmatrix} p&1&0&0 \\ q&0&0&0 \\ 1&0&1&0\\1&0&1&1\end{bmatrix}\)
代码：
Code
L.n=1,L.m=4;
R.n=R.m=4;
L.Mat[1][1]=1;L.Mat[1][2]=1;L.Mat[1][3]=2;L.Mat[1][4]=1;
R.Mat[1][1]=p;R.Mat[1][2]=1;R.Mat[1][3]=0;R.Mat[1][4]=0;
R.Mat[2][1]=q;R.Mat[2][2]=0;R.Mat[2][3]=0;R.Mat[2][4]=0;
R.Mat[3][1]=1;R.Mat[3][2]=0;R.Mat[3][3]=1;R.Mat[3][4]=0;
R.Mat[4][1]=1;R.Mat[4][2]=0;R.Mat[4][3]=1;R.Mat[4][4]=1;
Matrix ans=L*QuickPow(R,n-2);
printf("%lld\n",ans.Mat[1][1]);
矩阵加速入门6
思路：
多一个 \(n^2\) ，考虑在原始矩阵构造进去 \(n^2\)，思考如何通过加速矩阵得到\(f_{n+1}\)
\(f_{n+1} = p*f_n+q*f_{n-1}+(n+1)^2+n+1+1\)
\(~~~~~~~~\) \(= p*f_n+q*f_{n-1}+n^2+2*n+1+n+1+1\)
\(~~~~~~~~\) \(= p*f_n+q*f_{n-1}+n^2+3*n+3\)
如此就得到了 \(f_{n+1}\) 的式子。
\((n+1)^2\) 就等于 \(n^2+2*n+1\)
原始矩阵：
\(\begin{bmatrix} &f_2 & f_1 &2^2& 2 & 1 \end{bmatrix}\)
加速矩阵：
\(\begin{bmatrix} p&1&0&0&0 \\ q&0&0&0&0 \\ 1&0&1&0&0\\3&0&2&1&0\\3&0&1&1&1\end{bmatrix}\)
代码：
Code
L.n=1,L.m=5;
R.n=R.m=5;
L.Mat[1][1]=1;L.Mat[1][2]=1;L.Mat[1][3]=4;L.Mat[1][4]=2;L.Mat[1][5]=1;
R.Mat[1][1]=p;R.Mat[1][2]=1;R.Mat[1][3]=0;R.Mat[1][4]=0;R.Mat[1][5]=0;
R.Mat[2][1]=q;R.Mat[2][2]=0;R.Mat[2][3]=0;R.Mat[2][4]=0;R.Mat[2][5]=0;
R.Mat[3][1]=1;R.Mat[3][2]=0;R.Mat[3][3]=1;R.Mat[3][4]=0;R.Mat[3][5]=0;
R.Mat[4][1]=3;R.Mat[4][2]=0;R.Mat[4][3]=2;R.Mat[4][4]=1;R.Mat[4][5]=0;
R.Mat[5][1]=3;R.Mat[5][2]=0;R.Mat[5][3]=1;R.Mat[5][4]=1;R.Mat[5][5]=1;
Matrix ans=L*QuickPow(R,n-2);
printf("%lld\n",ans.Mat[1][1]);
矩阵加速入门7
思路：
这应该是最复杂的一道题了，如 \(6\) 题，考虑在原始矩阵构造进去 \(n^3\)，思考如何通过加速矩阵得到\(f_{n+1}\)
\(f_{n+1} = a*f_n+b*f_{n-1}+c*(n+1)^3+d*(n+1)^2+e\)
\(~~~~~~~~\) \(= a*f_n+b*f_{n-1}+c*(n^3+3*n^2+3*n+1)+d*(n^2+2*n+1)+e\)
\(~~~~~~~~\) \(= a*f_n+b*f_{n-1}+c*n^3+3*c*n^2+3*c*n+c+d*n^2+2*d*n+d+e\)
\(~~~~~~~~\) \(= a*f_n+b*f_{n-1}+c*n^3+(3*c+d)*n^2+(3*c+2*d)*n+c+d+e\)
如此就得到了 \(f_{n+1}\) 的式子。
原始矩阵：
\(\begin{bmatrix} &f_2 & f_1&2^3 &2^2& 2& 1 \end{bmatrix}\)
加速矩阵：
\(\begin{bmatrix} a&1&0&0&0&0 \\ b&0&0&0&0&0 \\ c&0&1&0&0&0\\d+3*c&0&3&1&0&0\\2*d+3*c&0&3&2&1&0\\c+d+e&0&1&1&1&1\end{bmatrix}\)
代码：
Code
L.n=1,L.m=6;
R.n=R.m=6;
L.Mat[1][1]=1;L.Mat[1][2]=1;L.Mat[1][3]=8;L.Mat[1][4]=4;L.Mat[1][5]=2;L.Mat[1][6]=1;
R.Mat[1][1]=a;R.Mat[1][2]=1;R.Mat[1][3]=0;R.Mat[1][4]=0;R.Mat[1][5]=0;R.Mat[1][6]=0;
R.Mat[2][1]=b;R.Mat[2][2]=0;R.Mat[2][3]=0;R.Mat[2][4]=0;R.Mat[2][5]=0;R.Mat[2][6]=0;
R.Mat[3][1]=c;R.Mat[3][2]=0;R.Mat[3][3]=1;R.Mat[3][4]=0;R.Mat[3][5]=0;R.Mat[3][6]=0;
R.Mat[4][1]=d+3*c;R.Mat[4][2]=0;R.Mat[4][3]=3;R.Mat[4][4]=1;R.Mat[4][5]=0;R.Mat[4][6]=0;
R.Mat[5][1]=d*2+3*c;R.Mat[5][2]=0;R.Mat[5][3]=3;R.Mat[5][4]=2;R.Mat[5][5]=1;R.Mat[5][6]=0;
R.Mat[6][1]=c+d+e;R.Mat[6][2]=0;R.Mat[6][3]=1;R.Mat[6][4]=1;R.Mat[6][5]=1;R.Mat[6][6]=1;
Matrix ans=L*QuickPow(R,n-2);
printf("%lld\n",ans.Mat[1][1]);
矩阵加速入门8
思路：
比较水的一道题，只需修改初始矩阵即与 \(5\) 题无区别。
原始矩阵：
\(\begin{bmatrix} &b(f_2) &a(f_1) & 2 & 1 \end{bmatrix}\)
加速矩阵：
\(\begin{bmatrix} p&1&0&0 \\ q&0&0&0 \\ 1&0&1&0\\1&0&1&1\end{bmatrix}\)
代码：
Code
L.n=1,L.m=6;
R.n=R.m=6;
L.Mat[1][1]=k2;L.Mat[1][2]=k1;L.Mat[1][3]=2;L.Mat[1][4]=1;
R.Mat[1][1]=p;R.Mat[1][2]=1;R.Mat[1][3]=0;R.Mat[1][4]=0;
R.Mat[2][1]=q;R.Mat[2][2]=0;R.Mat[2][3]=0;R.Mat[2][4]=0;
R.Mat[3][1]=1;R.Mat[3][2]=0;R.Mat[3][3]=1;R.Mat[3][4]=0;
R.Mat[4][1]=1;R.Mat[4][2]=0;R.Mat[4][3]=1;R.Mat[4][4]=1;
Matrix ans=L*QuickPow(R,n-2);
printf("%lld\n",ans.Mat[1][1]);
总结
失误巨大，将每题的 \(n\) 都开成了 \(int\)，结果 \(AK\) --> 爆零，是一次惨痛的教训。
考后悲伤没有用，希望以后读题，打代码一定细心仔细，不再犯此类低级错误！
标签：begin,end,Mat,突袭,矩阵,bmatrix,ans,初二 From： https://www.cnblogs.com/firephonenix/p/16796061.html