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

分类标签 Tags 点此展开 

最简单的矩阵快速幂优化DP,

退出斐波那契的矩阵然后跑矩阵快速幂就好,

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 void read(int &n)
 8 {
 9     char c='+';int x=0;bool flag=0;
10     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
11     while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}
12     flag==1?n=-x:n=x;
13 }
14 void Matrix_mul(int a[2][2],int b[2][2],int mod)
15 {
16     int c[2][2];
17     memset(c,0,sizeof(c));
18     for(int i=0;i<2;i++)
19         for(int j=0;j<2;j++)
20             for(int k=0;k<2;k++)
21                 c[i][j]=(c[i][j]+(a[i][k]*b[k][j])%mod)%mod;
22     for(int i=0;i<2;i++)
23         for(int j=0;j<2;j++)
24             a[i][j]=c[i][j];
25 }
26 int Matrix_fastpow(int n,int q)
27 {
28     int a[2][2]={1,1,1,0};
29     int ans[2][2]={1,0,1,0};
30     while(n)
31     {
32         if(n&1)
33             Matrix_mul(ans,a,q);
34         Matrix_mul(a,a,q);
35         n>>=1;
36     }
37     //cout<<ans[0][1]<<endl;
38     return ans[0][1];
39 }
40 int main()
41 {
42     int T,n,q;
43     read(T);
44     while(T--)
45     {
46         read(n);read(q);
47         n++;
48         printf("%d\n",Matrix_fastpow(n,q));
49     }
50     return 0;
51 }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • SDOI 2018二轮题解(除Day2T1)

    然鹅学了不到一个月文化课再回来看OI的东西有一种恍如隔世的感觉,烤前感觉也没啥可复习的,就补一补去年二轮的题吧。

    attack
  • 洛谷P4180 [Beijing2010组队]次小生成树Tree

    题目描述 小C最近学了很多最小生成树的算法,Prim算法、Kurskal算法、消圈算法等等。正当小C洋洋得意之时,小P又来泼小C冷水了。小P说,让小C求出一个无...

    attack
  • 洛谷P2312 解方程(暴力)

    对于\(a[i]\)取模之后再判断就行了。注意判断可能会出现误差,可以多找几个模数

    attack
  • 挖掘机技术哪家强(c++实现)

    描述:为了用事实说明挖掘机技术到底哪家强,组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

    用户2038589
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear
  • POJ Test for Job(DAG上拓扑排序)

           题意是给了n个点,m条边(单向边),然后每个点都有一个点权(存在负权),问从入度为0的点开始到出度为0的点,最大的权值和为多少。

    Ch_Zaqdt
  • leetcode 204题求素数个数

    Count the number of prime numbers less than a non-negative number, n

    流川疯
  • POJ 3020 Antenna Placement(二分图最小边覆盖)

           题意是有一个n*m的地图,图中'*'表示城市,现在要给每个城市覆盖无线,需要安装基站,每个基站最多只能覆盖相邻的两个城市,也就是1*2或者2*1的...

    Ch_Zaqdt
  • 水果Fruit(母函数) - HDU 2152

    转眼到了收获的季节,由于有TT的专业指导,Lele获得了大丰收。特别是水果,Lele一共种了N种水果,有苹果,梨子,香蕉,西瓜……不但味道好吃,样子更是好看。 ...

    ACM算法日常
  • 「CodeForces - 598B」Queries on a String

    字符串s(1 ≤ |s| ≤ 10 000),有m(1 ≤ m ≤ 300)次操作,每次给l,r,k,代表将r位置插入l位置前,执行k(1 ≤ k ≤ 1 00...

    饶文津

扫码关注云+社区

领取腾讯云代金券