首页 > 代码库 > 1250 Fibonacci数列（矩阵乘法快速幂）
1250 Fibonacci数列（矩阵乘法快速幂）
1250 Fibonacci数列
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 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
code
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 5 using namespace std; 6 7 const int N = 2; 8 int mod; 9 10 struct Matrix{11 int a[N][N];12 Matrix(){13 this->clear();14 }15 void clear(){16 memset(a,0,sizeof(a));17 }18 void setone(){19 this->clear();20 for (int i=0; i<N; ++i)21 a[i][i] = 1;22 }23 Matrix operator * (const Matrix &x) const 24 {25 Matrix c;26 for (int k=0; k<N; k++)27 for (int i=0; i<N; ++i)28 for (int j=0; j<N; ++j)29 c.a[i][j] = (c.a[i][j]+1ll*a[i][k]*x.a[k][j])%mod;30 return c;31 }32 };33 34 int fibn(int n)35 {36 Matrix x,s;37 x.a[0][0] = x.a[0][1] = x.a[1][0] = 1;38 s.setone();39 for (; n; n>>=1)40 {41 if (n&1) s = s*x;42 x = x*x; 43 }44 return (s.a[0][0]+s.a[0][1])%mod;45 }46 int main()47 {48 int t,n;49 scanf("%d",&t);50 while (t--)51 {52 scanf("%d%d",&n,&mod);53 n++;54 if (n==1||n==2) printf("%d\n",1);55 else printf("%d\n",fibn(n-2));56 }57 return 0;58 }
1250 Fibonacci数列（矩阵乘法快速幂）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。