HDU 1757 A Simple Math Problem（矩阵快速幂）

题目链接

题意 :给你m和k，让你求f(k)%m。如果k<10,f(k) = k，否则 f(k) = a0 * f(k-1) + a1 * f(k-2) + a2 * f(k-3) + …… + a9 * f(k-10);
思路：先具体介绍一下矩阵快速幂吧，刚好刚刚整理了网上的资料。可以先了解一下这个是干嘛的，怎么用。

这个怎么弄出来的我就不说了，直接看链接吧，这实在不是我强项，点这儿，这儿也行

 //HDU 1757

 #include <iostream>

 #include <stdio.h>

 using namespace std;

 struct matrix

 {

     int m[][] ;

 } b,tp,res,init ;

 int n,m ;

 matrix Mul(matrix a,matrix b)

 {

     matrix c ;

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

     {

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

         {

             c.m[i][j] =  ;

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

             {

                 c.m[i][j] += (a.m[i][k] * b.m[k][j]) % m ;

                 c.m[i][j] %= m ;

             }

         }

     }

     return c ;

 }

 matrix matrix_mi(matrix p,int k)

 {

     matrix t = res;

     for(int i =  ; i <=  ; i++) t.m[i][i] =  ;

     while(k)

     {

         if(k & )

             t = Mul(t,p) ;

         k >>=  ;

         p = Mul(p,p) ;

     }

     return t ;

 }

 void Init()

 {

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

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

             if(i- == j)

                 init.m[i][j]=;

             else

                 init.m[i][j]=;

 }

 int main()

 {

     Init() ;

     while(~scanf("%d %d",&n,&m))

     {

         b = init ;

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

             scanf("%d",&b.m[][i]) ;

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

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

                 if(i==j)

                     res.m[i][j] =  ;

                 else

                     res.m[i][j] =  ;

         if(n >= )

         {

             int sum =  ;

             tp = matrix_mi(b,n-) ;

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

                 sum += (tp.m[][i] * (-i))%m ;

             printf("%d\n",sum%m) ;

         }

         else printf("%d\n",n%m) ;

     }

     return ;

 }

巴特西

HDU 1757 A Simple Math Problem（矩阵快速幂）

最新文章

热门文章