Fib数列问题（项数很大）

用fib(n)表示斐波那契数列的第n项，现在要求你求fib(n) mod m。fib(1)= 1, fib(2)= 1。

输入格式

输入2个整数n(1≤n≤10), m(2≤m≤10000000)。

输出格式

输出fib(n)对m取模的值。

样例输入1

样例输出1

样例输入2

样例输出2

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 struct matrix

 {

     LL a[][];

 };

 matrix matrix_mul(matrix A, matrix B, LL mod)// 2 个矩阵相乘

 {

     matrix C;

     int i,j,k;

     for(i=;i<=;i++)

     {

         for(j=;j<=;j++)

         {

             C.a[i][j]=;

             for(k=;k<=;k++)

             {

                 C.a[i][j]+=A.a[i][k]*B.a[k][j]%mod;

                 C.a[i][j]%=mod;

             }

         }

     }

     return C;

 }

 matrix unit() // 返回一个单位矩阵

 {

     matrix res;

     int i,j;

     for(i=;i<=;i++)

     {

         for(j=;j<=;j++)

         {

             if(i==j)

             res.a[i][j]=;

             else

             res.a[i][j]=;

         }

     }

     return res;

 }

 matrix matrix_pow(matrix A, LL n, LL mod)// 快速求矩阵 A 的 n 次方

 {

     matrix res=unit(),temp=A;

     for(;n;n/=)

     {

         if(n&)

         res=matrix_mul(res,temp,mod);

         temp=matrix_mul(temp,temp,mod);

     }

     return res;

 }

 int main()

 {

     LL n,m;

     scanf("%lld %lld",&n,&m);

     if(n<)

     printf("1\n");

     else

     {

         matrix A,B,C;

         A.a[][]=; A.a[][]=;

         A.a[][]=; A.a[][]=;

         B.a[][]=;

         B.a[][]=;

         C=matrix_mul( matrix_pow(A,n-,m), B, m);

         printf("%lld\n", C.a[][]);

     }

     return ;

 }

-