UVA 10655 Contemplation! Algebra（矩阵乘法）

本文主要是介绍UVA 10655 Contemplation! Algebra（矩阵乘法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意:求$a^n + b^n$。
输入三个数，p，q，n
p = a+b;
q = a*b;
n不用说了。

可以把前几项列出来
$a^0 + b^0 = 2$;
$a^1 + b^1 = a+b$;
$a^2 + b^2 = (a+b)*(a+b) - 2*a*b$
$a^3 + b^3 = (a^2+b^2)*(a+b) - (a^2+b^2)*a*b$

可以发现$f(n) = f(n-1)*(a+b) - f(n-2)*(a*b)$;
我们就可以构造出矩阵：（其实就是变形的斐波那契）
$\bigl( \begin{smallmatrix} 2 & a+b \\ 0 & 0 \end{smallmatrix} \bigr)$ $\bigl( \begin{smallmatrix} 0 & -a*b \\ 1 & a+b \end{smallmatrix} \bigr)$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;struct Matrix
{long long m[2][2];int n;Matrix(int x){n = x;for(int i=0;i<n;i++)for(int j=0;j<n;j++)m[i][j] = 0;}Matrix(int _n,int a[2][2]){n = _n;for(int i=0;i<n;i++)for(int j=0;j<n;j++){m[i][j] = a[i][j];}}
};
Matrix operator *(Matrix a,Matrix b)
{int n = a.n;Matrix ans = Matrix(n);for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int k=0;k<n;k++){ans.m[i][j] += a.m[i][k]*b.m[k][j];}return ans;
}
Matrix operator ^(Matrix a,LL k)
{int n = a.n;Matrix c(n);int i,j;for(i=0;i<n;i++)for(j=0;j<n;j++)c.m[i][j] = (i==j);for(;k;k>>=1){if(k&1)c=c*a;a = a*a;}return c;
}int main(void)
{LL p,q,n;while(scanf("%lld%lld%lld",&p,&q,&n)==3){int a[2][2] = { 2,p,0,0};int b[2][2] = { 0,-q,1,p};Matrix A(2,a);Matrix B(2,b);A = A*(B^n);LL ans = A.m[0][0];printf("%lld\n",ans);}return 0;
}

这篇关于UVA 10655 Contemplation! Algebra（矩阵乘法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---