矩阵快速幂-白红宇

矩阵快速幂

阅读量：5047 次

发布时间：2019-06-12

本文共 2903 字，大约阅读时间需要 9 分钟。

矩阵快速幂，对于很大的递推式需要要用到；

贴几个题http://poj.org/problem?id=3070

#include
     
      #include
      
       #include
       
        #include
        
         const int M=2;const int mod=10000;struct node{    int m[M][M];    node operator*(node const &b)const{        node res;        memset(res.m,0,sizeof(res.m));        for(int i=0;i
         
          m[i][k]*b.m[k][j])%mod;        return res;    }};node quick(node base,int b){    node t;    t.m[1][1]=t.m[0][0]=1;    t.m[1][0]=t.m[0][1]=0;    while(b)    {        if(b&1)            t=t*base;        b>>=1;        base=base*base;    }    return t;}int main(){    node s;    s.m[0][0]=s.m[0][1]=s.m[1][0]=1;    s.m[1][1]=0;    int n;    while(~scanf("%d",&n)&&n!=-1)    {        if(n==0)        {            printf("0\n");            continue;        }        node sum;        sum=quick(s,n);        printf("%d\n",sum.m[0][1]);    }    return 0;}

http://acm.hdu.edu.cn/showproblem.php?pid=1575

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long ll;int n;const int mod=9973;const int M=10;struct node{    int m[M][M];    node operator*(node const &b)const{        node res;        memset(res.m,0,sizeof(res.m));        for(int i=0;i
         
          m[i][k]*b.m[k][j])%mod;        return res;    }};int quick(node &a,int k){    node t;    memset(t.m,0,sizeof(t.m));    for(int i=0;i
          
           >=1; a=a*a; } ll sum=0; for(int i=0;i

http://acm.hdu.edu.cn/showproblem.php?pid=2256

/*题目要求的是(sqrt(2)+sqrt(3))^2n %1024向下取整的值(sqrt(2)+sqrt(3))^2n=((sqrt(2)+sqrt(3))^2)n=(5+2*sqrt(6))^n改式子一定可以表示为f(x)=a[x]+b[x]*sqrt(6);所以f(x)=f(x-1)*(5+2*sqrt(6));既f(x)=(5+2*sqrt(6)*(a[x-1]+b[x-1]*sqrt(6)));|5  12|*|a[n-1]|=|a[n]||2  5 |*|b[n-1]|=|b[n]|因此矩阵快速幂；然后就是取数的问题了，向下取整 由(5+2*sqrt(6))^n=a[n]+b[n]*sqrt(6)    (5-2*sqrt(6))^n=a[n]-b[n]*sqrt(6);所以(5+2*sqrt(6))^n+(5-2*sqrt(6))^n=2*a[n];因为(5-2*sqrt(6))^n约等于0；所以(5+2*sqrt(6))^n+0=2*a[n];所以(5+2*sqrt(6))^n=2*a[n]-1(向下取整）*/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int M=2;const int mod=1024;const double P=sqrt((double)6);struct node{    int m[M][M];    node operator*(const node &b)const{        node res;        memset(res.m,0,sizeof(res.m));        for(int i=0;i
          
           m[i][k]*b.m[k][j])%mod; return res; }};int quick(node &a,int b){ if(b==1) return 9; node t; memset(t.m,0,sizeof(t.m)); for(int i=0;i
           
            >=1; a=a*a; } int suma=0; suma+=(t.m[0][0]*5+t.m[0][1]*2)%mod; return(2*suma-1)%mod;}int main(){ int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); node a; memset(a.m,0,sizeof(a.m)); a.m[0][0]=5; a.m[0][1]=12; a.m[1][0]=2; a.m[1][1]=5; printf("%d\n",quick(a,n)); } return 0;}