【矩阵乘法】广义斐波那契数列

炸鸡

2017-04-26

矩阵乘法

这道题解法或许有很多吧反正蒟蒻的我写了矩阵快速幂

第一次写矩阵乘法先贴原理：若两个矩阵A、B可进行矩乘，则需要A的列数和B的行数一致若A为n行p列的矩阵，B为p行m列的矩阵

$(AB)_{ij}=\sum_{k=1}^pA_{ik}*B_{kj}$

那么回到题目中用矩阵表示数列的通项公式

$\left(\begin{matrix}a_n\\a_{n-1}\end{matrix}\right)=\left(\begin{matrix}p&q\\1&0\end{matrix}\right)*\left(\begin{matrix}a_{n-1}\\a_{n-2}\end{matrix}\right)$

由此

$\left(\begin{matrix}a_n\\a_{n-1}\end{matrix}\right)=\left(\begin{matrix}p&q\\1&0\end{matrix}\right)^{n-2}*\left(\begin{matrix}a_2\\a_1\end{matrix}\right)$

那么可以使用快速幂求解矩阵的幂

代码如下（PS：建议定义矩阵的结构体并重载乘法）

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
 
using namespace std;
#define LL long long
LL p,q,x,y,n,m;
struct matrix{
	LL s[4][4];
	
	matrix(){
		memset(s,0,sizeof s);
	}
	
	matrix operator * (const matrix &n) const {
		matrix c;
		for (int i=1;i<=3;++i)
			for (int j=1;j<=3;++j)
				for (int k=1;k<=3;++k)
					c.s[i][j]=(c.s[i][j]+s[i][k]*n.s[k][j])%m;
		return c;
	}
}
ans,k,l;
matrix pow(matrix k,LL x){
	if (x==1) return k;
	
	matrix u=pow(k,x>>1);
	if ((x&1)==1) return u*u*k;
	else return u*u;
}
int main(){
	scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&x,&y,&n,&m);
	
	k.s[1][1]=p;
	k.s[1][2]=q;
	k.s[2][1]=1;
	k.s[2][2]=0;
	l.s[1][1]=y;
	l.s[2][1]=x;
	ans=pow(k,n-2)*l;
	
	printf("%lld\n",ans.s[1][1]);
	
	return 0;
}