题解 P1349 【广义斐波那契数列】

yybyyb · 2017-07-13 17:32:47 · 题解

感觉这个斐波那契和普通的那个区别并不是很大

只需要捣鼓出矩阵即可

首先，容易推出

接下来直接求解就行了

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 10
#define ll long long
ll p,q,a1,a2,n,MOD;
struct yl//矩阵 
{
       int n;//大小
       long long g[MAX][MAX];  
}A;
yl operator *(yl a,yl b)//定义乘法 
{
       int n=a.n;
       yl cool;
       memset(cool.g,0,sizeof(cool.g));
       for(int i=1;i<=n;++i)
               for(int j=1;j<=n;++j)
                 for(int k=1;k<=n;++k)
                        cool.g[i][j]=(cool.g[i][j]+1ll*a.g[i][k]*b.g[k][j]%MOD)%MOD;
       cool.n=n;
       return cool;
}
void write(yl a)
{
       int n=a.n;
       for(int i=1;i<=n;++i)
       {
           for(int j=1;j<=n;++j)
              cout<<a.g[i][j]<<' ';
           cout<<endl;
       }
}
yl Pow(yl a,long long b)//a的b次方
{
       if(b==1)return a;
       yl s=Pow(a,b/2);
       s.n=a.n;
       s=s*s;
       if(b&1)s=s*a;
       return s;
}
int main()
{
        cin>>p>>q>>a1>>a2>>n>>MOD;
        A.n=2;
        A.g[1][1]=p;A.g[1][2]=1;
        A.g[2][1]=q;A.g[2][2]=0;
        yl S=Pow(A,n-2);
        A.g[1][1]=a2;A.g[1][2]=a1;
        A.g[2][1]=A.g[2][2]=0;
        A=A*S;
        cout<<(A.g[1][1])%MOD<<endl;
        return 0;
}