专栏首页算法修养HDU 5667 Sequence(矩阵快速幂)

HDU 5667 Sequence(矩阵快速幂)

Problem Description Holion August will eat every thing he has found.

Now there are many foods,but he does not want to eat all of them at once,so he find a sequence.

fn=⎧⎩⎨⎪⎪1,ab,abfcn−1fn−2,n=1n=2otherwise

He gives you 5 numbers n,a,b,c,p,and he will eat fn foods.But there are only p foods,so you should tell him fn mod p.

Input The first line has a number,T,means testcase.

Each testcase has 5 numbers,including n,a,b,c,p in a line.

1≤T≤10,1≤n≤1018,1≤a,b,c≤109,p is a prime number,and p≤109+7.

Output Output one number for each case,which is fn mod p.

Sample Input 1 5 3 3 3 233

Sample Output 190

用矩阵快速幂的时候,注意对p-1取余 递推式:a[n]=c*a[n-1]+a[n-2]+1;

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;
typedef long long int LL;
struct Node
{
    LL a[3][3];
}A,B,C;
LL p,n,a,b,c;
Node multiply(Node a,Node b)
{
    Node c;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            c.a[i][j]=0;
            for(int k=0;k<3;k++)
            {
                (c.a[i][j]+=(a.a[i][k]*b.a[k][j])%(p-1))%=(p-1);
            }
        }
    }
    return c;
}
Node get(Node a,LL x)
{
    Node c;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
             c.a[i][j]=(i==j?1:0);
    for(x;x;x>>=1)
    {
        if(x&1) c=multiply(c,a);
        a=multiply(a,a);
    }
    return c;
}
LL quick(LL x,LL y)
{
    if(n>1&&y==0) y=p-1;
    LL ans=1;
    for(y;y;y>>=1)
    {
        if(y&1)  ans=(ans*x)%p;
        x=(x*x)%p;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld%lld%lld%lld",&n,&a,&b,&c,&p);
        A.a[0][0]=0;A.a[1][0]=0;A.a[2][0]=1;
        B.a[0][0]=c; B.a[0][1]=1; B.a[0][2]=1;
        B.a[1][0]=1; B.a[1][1]=0; B.a[1][2]=0;
        B.a[2][0]=0; B.a[2][1]=0; B.a[2][2]=1;
        if(n==1) {cout<<1<<endl;continue;}
        B=get(B,n-1);
        B=multiply(B,A);
        LL num=((B.a[0][0]%(p-1))*(b%(p-1)))%(p-1);
        //cout<<num<<endl;
        cout<<quick(a,num)<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 2604 Queuing(矩阵快速幂)

    Queuing Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (...

    ShenduCC
  • HDU 2157 How many ways??(简单线性DP | | 矩阵快速幂)

    题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2157 这道题目很多人的题解都是矩阵快速幂写的,矩阵快速幂倒...

    ShenduCC
  • HUST 1606 - Naive

    1606 - Naive 时间限制:3秒 内存限制:128兆 779 次提交 138 次通过 题目描述 Give you a positive in...

    ShenduCC
  • 选择法排序和把一个整数插入以排好的序的数组中

    栋先生
  • uva 165 Stamps

      求能贴出的最大连续区间,即[1, max_value]这个区间内的所有面额都能贴出来。

    若羽
  • LeetCode 835. 图像重叠

    给出两个图像 A 和 B ,A 和 B 为大小相同的二维正方形矩阵。(并且为二进制矩阵,只包含0和1)。

    Michael阿明
  • 业界 | 用Python做数据科学时容易忘记的八个要点!

    虽然我们在StackOverflow或其他网站上查找答案是很正常的事情,但这样做确实比较花时间,也让人怀疑你是否完全理解了这门编程语言。

    大数据文摘
  • Python将二维列表list的数据输出(TXT,Excel)

    利用Python处理数据时,处理完成后输出结果为二维的列表,如果我们想把这个列表输出到Excel中形成格式化的数据,其实和输出到TXT文件大同小异。

    砸漏
  • centOS 7下python2升级为p

    ###  centos 7下python自带版本为2.7,但是今天需要用到3,所以升级了一下

    py3study
  • 数据库默认排序

    目标:理解oracle,mysql,sqlserve 三个数据库中的排序效率问题!

    斯文的程序

扫码关注云+社区

领取腾讯云代金券