传送门 题目描述 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<=10 9 , 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<=10 9 , 1<=q<=30000
第一次矩阵快速幂。。 找到一个比较好的矩阵乘法和矩阵快速幂的课件，如何设计矩阵在里面说的很清楚 对于这道题，假设我们已经知道了f(n-2)和f(n-1)（就像下面这样），如果我们想得到f(n)，怎么做呢？
[f(n−1)f(n−2)] 按照课件中的方法，我们设计出矩阵： [1110] 用这两个矩阵相乘就能得到 [f(n)f(n−1)] 这样我们就能解决这道题了。CODE：
#include<cstdio> #include<cstring> int T,n,q; struct Matrix { int a[2][2]; inline void init(){a[0][0]=a[0][1]=a[1][0]=1,a[1][1]=0;} }; inline Matrix operator *(Matrix a,Matrix b) { Matrix ans; memset(ans.a,0,sizeof(ans.a)); for(int i=0;i<=1;i++) for(int j=0;j<=1;j++) for(int k=0;k<=1;k++) ans.a[i][j]=(ans.a[i][j]+a.a[i][k]*b.a[k][j])%q; return ans; } inline Matrix pow() { Matrix a,ans,tmp; a.init(),ans.init(); tmp.a[0][0]=tmp.a[1][0]=tmp.a[1][1]=1,tmp.a[0][1]=0; for(n--;n;n>>=1,a=a*a) if(n&1) ans=ans*a; ans=ans*tmp; return ans; } int main() { scanf("%d",&T); while(T--) { scanf("%d%d",&n,&q); if(n<=1){printf("%d\n",1%q);continue;} if(q<=1){puts("0");continue;} Matrix ans=pow(); printf("%d\n",ans.a[1][0]); } return 0; }