首页 > 代码库 > [codevs]1250斐波那契数列<矩阵dp>
[codevs]1250斐波那契数列<矩阵dp>
题目描述 Description
定义:f0=f1=1, fn=fn-1+fn-2(n>=2)。{fi}称为Fibonacci数列。
输入n,求fn mod q。其中1<=q<=30000。
输入描述 Input Description
第一行一个数T(1<=T<=10000)。
以下T行,每行两个数,n,q(n<=109, 1<=q<=30000)
输出描述 Output Description
文件包含T行,每行对应一个答案。
样例输入 Sample Input
3
6 2
7 3
7 11
样例输出 Sample Output
1
0
10
数据范围及提示 Data Size & Hint
1<=T<=10000
n<=109, 1<=q<=30000
感谢:这道题卡了一天,最后发现自己是被坑了,我一直以为斐波那契数列f0=0,f1=f2=1,结果这是f0=f1=1;
好吧这只是我智障了,我还是来说说矩阵怎么做吧
首先矩阵乘法的定义:
A和B两个矩阵乘出来是
知道矩阵是怎么样乘后就可以来解决这道题,我们定义一个初始矩阵和单位矩阵
而fn+fn-1=fn+1,所以这就是这道题的关键了
例如我要求f6 就要用初识矩阵*b^5,而初识矩阵ans[1][1]=f1=1,ans[1][2]=f0=1
当数据比较大的时候这个b^n-1次方可能就会爆,所以这又要用到快速幂
然后我们来看个快速幂模板
//求a^b %c void done(int a,int b,int c) {
ans=1; while(b) { if(b&1) ans=(ans*a)%c; a=(a*a)%c; b>>=1; } }
有了这两个知识,我们就可以实现矩阵快速幂了
代码如下:
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<iostream> 5 using namespace std; 6 7 long long ans[3][2],c[5][5],b[5][5]; 8 long long n,m,t; 9 10 void dod(int n) 11 { 12 while(n) 13 { 14 if(n&1)//判断n的奇偶性 15 { 16 for(int i=1;i<=2;i++) 17 for(int j=1;j<=1;j++) 18 { 19 for(int k=1;k<=2;k++) 20 c[i][j]=(c[i][j]+ans[k][j]*b[i][k])%m;//这个地方的i,j,k建议画图分析 21 } 22 for(int i=1;i<=2;i++) 23 for(int j=1;j<=1;j++) 24 { 25 ans[i][j]=c[i][j]; 26 c[i][j]=0; 27 } 28 } 29 for(int i=1;i<=2;i++) 30 for(int j=1;j<=2;j++) 31 { 32 for(int k=1;k<=2;k++) 33 c[i][j]=(c[i][j]+b[i][k]*b[k][j])%m; 34 } 35 for(int i=1;i<=2;i++) 36 for(int j=1;j<=2;j++) 37 { 38 b[i][j]=c[i][j]; 39 c[i][j]=0; 40 } 41 n>>=1; 42 43 } 44 45 } 46 47 int main() 48 { 49 cin>>t; 50 while(t--) 51 { 52 scanf("%lld%lld",&n,&m); 53 b[1][1]=b[1][2]=b[2][1]=1; 54 ans[1][1]=ans[2][1]=1; 55 b[2][2]=0; 56 n--;//fn只需要初识矩阵*b^n-1 57 dod(n); 58 printf("%lld\n",ans[1][1]%m); 59 } 60 61 }
讲题略水,如有错误,望诸位大佬指出
[codevs]1250斐波那契数列<矩阵dp>
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。