HDU-6395 Sequence（矩阵快速幂）

最新推荐文章于 2019-09-21 21:29:55 发布

进阶的萌新

最新推荐文章于 2019-09-21 21:29:55 发布

阅读量206

点赞数

分类专栏： C++

本文链接：https://blog.csdn.net/JD_coder/article/details/89191699

版权

C++ 专栏收录该内容

28 篇文章

订阅专栏

本文介绍了一种使用矩阵快速幂求解特定形式数列第n项的算法，适用于形如F[n] = A*F[n-1] + B*F[n-2] + C*F[n-3] + D的数列。通过定义特定的矩阵和运用快速幂技巧，可以在O(log n)的时间复杂度内高效计算出数列的任意一项。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

Sequence

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2610 Accepted Submission(s): 1018

Problem Description

Let us define a sequence as below

Your job is simple, for each task, you should output Fn module 109+7.

Input

The first line has only one integer T, indicates the number of tasks.

Then, for the next T lines, each line consists of 6 integers, A , B, C, D, P, n.

1≤T≤200≤A,B,C,D≤1091≤P,n≤109

Sample Input

3 3 2 1 3 5

3 2 2 2 1 4

Sample Output

36 24

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
const int mod = 1e9+7;

struct node
{
    LL mt[3][3];
}a,b;
int a1,b1,c1,d1,p1,n1;

node mult(node x,node y)
{
    node z;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
        {
            z.mt[i][j]=0;
            for(int k=0;k<3;k++)
                (z.mt[i][j]+=x.mt[i][k]*y.mt[k][j]%mod)%=mod;
        }
    return z;
}
inline void qpow()
{
    node z,temp;
    memset(b.mt,0,sizeof(b.mt));
    memset(z.mt,0,sizeof(z.mt));
    memset(a.mt,0,sizeof(a.mt));

    b.mt[0][0]=b1,b.mt[1][0]=a1;
    b.mt[2][0]=1;
    a.mt[0][0]=d1,a.mt[0][1]=c1;
    a.mt[0][2]=p1,a.mt[1][0]=1;
    a.mt[2][2]=1;

    temp=a;
    for(int i=0;i<3;i++)
        z.mt[i][i]=1;
    int k=3,s=0;

    while(k<=n1)
    {
        int c=1,New=p1/k;
        temp.mt[0][2]=New;
        a=temp;
        if(New!=0)
        {
            int u=p1/New;
            if(u>=n1)  u=n1;
            if(u!=k){
                c=u-k+1, k=u;
            }
        }
        else{
            c=n1-k+1, k=n1;
        }
        while(c)
        {
            if(c&1)  z=mult(a,z);
            if(c!=1) a=mult(a,a);
            c=c>>1;
        }
        if(s==0)  z=mult(z,b);
        k++,s++;
    }
    printf("%lld\n",z.mt[0][0]);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d%d%d",&a1,&b1,&c1,&d1,&p1,&n1);
        if(n1==1)
            printf("%d\n",a1);
        else if(n1==2)
            printf("%d\n",b1);
        else  qpow();
    }
    return 0;
}