1250 Fibonacci數(shù)列

?

?時間限制: 1 s ?空間限制: 128000 KB ?題目等級 : 鉆石 Diamond

題目描述?Description

定義：f0=f1=1,?fn=fn-1+fn-2(n>=2)。{fi}稱為Fibonacci數(shù)列。

輸入n，求fn?mod?q。其中1<=q<=30000。

輸入描述?Input Description

第一行一個數(shù)T(1<=T<=10000)。

以下T行，每行兩個數(shù)，n，q(n<=109,?1<=q<=30000)

輸出描述?Output Description

文件包含T行，每行對應一個答案。

樣例輸入?Sample Input

3

6?2

7?3

7?11

樣例輸出?Sample Output

1

0

10

數(shù)據(jù)范圍及提示?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 }

?

轉載于:https://www.cnblogs.com/mjtcn/p/7307954.html

總結

以上是生活随笔為你收集整理的1250 Fibonacci数列（矩阵乘法快速幂）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。