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

```#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 (...

• HDU 2157 How many ways??（简单线性DP | | 矩阵快速幂）

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

• HUST 1606 - Naive

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

• uva 165 Stamps

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

• LeetCode 835. 图像重叠

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

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

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

• Python将二维列表list的数据输出(TXT，Excel)

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

• centOS 7下python2升级为p

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

• 数据库默认排序

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