Codevs 1574 广义斐波那契数列(矩阵乘法)

1574 广义斐波那契数列

时间限制: 1 s

空间限制: 256000 KB

题目等级 : 钻石 Diamond

题目描述 Description

广义的斐波那契数列是指形如an=p*an-1+q*an-2的数列。今给定数列的两系数p和q，以及数列的最前两项a1和a2，另给出两个整数n和m，试求数列的第n项an除以m的余数。

输入描述 Input Description

输入包含一行6个整数。依次是p,q,a1,a2,n,m，其中在p,q,a1,a2整数范围内，n和m在长整数范围内。

输出描述 Output Description

输出包含一行一个整数，即an除以m的余数。

样例输入 Sample Input

1 1 1 1 10 7

样例输出 Sample Output

6

数据范围及提示 Data Size & Hint

数列第10项是55，除以7的余数为6。

分类标签 Tags

矩阵乘法数论

/*

矩阵乘法快速幂.

矩阵还是比较好推的.....

要时刻想清楚最后的答案记在哪儿.

然后W了好几次.

ans先赋值乘一次.n-1.

把答案放在后边的话A1到An显然乘了n-2次....

*/

#include<iostream>

#include<cstdio>

#define MAXN 3

#define LL long long

using namespace std;

LL p,q,a1,a2,n,m;

LL a[MAXN][MAXN],ans[MAXN][MAXN],c[MAXN][MAXN],b[MAXN][MAXN];

void mi(int n)

{

    while(n)

    {

        if(n&1)

        {

            for(int i=1;i<=2;i++)

              for(int j=1;j<=2;j++)

                for(int k=1;k<=2;k++)

                c[i][j]=(c[i][j]+ans[i][k]*b[k][j]%m)%m;

            for(int i=1;i<=2;i++)

              for(int j=1;j<=2;j++)

                ans[i][j]=c[i][j],c[i][j]=0;

        }

        for(int i=1;i<=2;i++)

          for(int j=1;j<=2;j++)

            for(int k=1;k<=2;k++)

              c[i][j]=(c[i][j]+b[i][k]*b[k][j]%m)%m;

        for(int i=1;i<=2;i++)

          for(int j=1;j<=2;j++)

            b[i][j]=c[i][j],c[i][j]=0;

        n>>=1;

    }

}

void slove()

{

    a[1][1]=a1,a[1][2]=a2;

    b[1][2]=ans[1][2]=q,b[2][1]=ans[2][1]=1,

    b[2][2]=ans[2][2]=p;

    mi(n);

    printf("%lld",(a[1][1]*ans[1][2]%m+a[1][2]*ans[2][2]%m)%m);

}

int main()

{

    scanf("%d%d%d%d",&p,&q,&a1,&a2);

    cin>>n;cin>>m;

    n-=3;

    slove();

    return 0;

}

/*

结果在前边.

多乘一次.

*/

#include<iostream>

#include<cstdio>

#define MAXN 3

#define LL long long

using namespace std;

LL p,q,a1,a2,n,m;

LL a[MAXN][MAXN],ans[MAXN][MAXN],c[MAXN][MAXN],b[MAXN][MAXN];

void mi(int n)

{

    while(n)

    {

        if(n&1)

        {

            for(int i=1;i<=2;i++)

              for(int j=1;j<=2;j++)

                for(int k=1;k<=2;k++)

                c[i][j]=(c[i][j]+ans[i][k]*b[k][j]%m)%m;

            for(int i=1;i<=2;i++)

              for(int j=1;j<=2;j++)

                ans[i][j]=c[i][j],c[i][j]=0;

        }

        for(int i=1;i<=2;i++)

          for(int j=1;j<=2;j++)

            for(int k=1;k<=2;k++)

              c[i][j]=(c[i][j]+b[i][k]*b[k][j]%m)%m;

        for(int i=1;i<=2;i++)

          for(int j=1;j<=2;j++)

            b[i][j]=c[i][j],c[i][j]=0;

        n>>=1;

    }

    /*for(int i=1;i<=2;i++)

      for(int j=1;j<=2;j++)

        for(int k=1;k<=2;k++)

          c[i][j]=(c[i][j]+a[i][k]*ans[k][j]%m)%m;*/

}

void slove()

{

    a[1][1]=a1,a[1][2]=a2;

    b[1][2]=ans[1][2]=q,b[2][1]=ans[2][1]=1,

    b[2][2]=ans[2][2]=p;

    mi(n);

    printf("%lld",(a[1][1]*ans[1][1]%m+a[1][2]*ans[2][1]%m)%m);

}

int main()

{

    scanf("%d%d%d%d",&p,&q,&a1,&a2);

    cin>>n;cin>>m;

    n-=2;

    slove();

    return 0;

}

巴特西

Codevs 1574 广义斐波那契数列(矩阵乘法)

最新文章

热门文章