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

【洛谷P1349】广义斐波那契数列【矩阵乘法】
L u o g u   l i n k Luogu~link Luogu link

分析:

显然矩乘
普通斐波那契 转移矩阵:
∣ 1 , 1 ∣ ∣ 1 , 0 ∣ |1,1|\\ |1,0| ∣1,1∣∣1,0∣
那么只需要把系数加上:
∣ p , 1 ∣ ∣ q , 0 ∣ |p,1|\\ |q,0| ∣p,1∣∣q,0∣
以及递推矩阵改为 [ a 2 , a 1 ] [a_2,a_1] [a2​,a1​]即可

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,Mod,a1,a2,p,q;
struct Matrix{
	ll G[4][4];
}ans,base;
Matrix operator *(Matrix A,Matrix B)
{
	Matrix res;
	memset(res.G,0,sizeof res.G);
	for(int k=1;k<=2;k++)
	for(int i=1;i<=2;i++)
		for(int j=1;j<=2;j++)
			(res.G[i][j]+=(A.G[i][k]%Mod)*(B.G[k][j]%Mod))%=Mod;
	return res;
}
void mul(ll k)
{
	while(k)
	{
		if(k&1) ans=ans*base;
		base=base*base;
		k>>=1;
	}
}
int main(){
	scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&a1,&a2,&n,&Mod);
	ans.G[1][1]=a2; ans.G[1][2]=a1;
	base.G[1][1]=p; base.G[1][2]=1;
	base.G[2][1]=q;
	mul(n-2);
	printf("%lld",ans.G[1][1]%Mod);
	return 0;
}
上一篇:JavaScript 闭包


下一篇:NodeJS中module.exports和exports的区别