求n^m 时间复杂度log(m)的算法(含矩阵)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 01 月 10 日

//求n^m 时间复杂度log(m)  
int calc(int n,int m){  
    int re=1;  
    while(m){  
       if(m&1)  
          re*=n;  
       n*=n;  
       m>>=1;  
    }  
    return re;  
}  
//求矩阵[n]^m 时间复杂度log(m)  
#include<cstring>  
#include<iostream>  
using namespace std;  
#define N 2  
#define MOD 10000  
struct Matrix  
{  
    int m[2][2];  
};  
void  matrixMultiplication(Matrix &res,int n)  
{  
    Matrix tm,tm1;  
    int i,j,k;  
    tm=res;  
    for (i=0;i<N;i++)  
        for (int j=0;j<N;j++)  
        {  
            res.m[i][j]=(i==j);  
        }  
    if(n==0){ return; }  
    while(n)  
    {  
          
        if(n&1)  
        {  
            memset(tm1.m,0,sizeof(tm1.m));  
            for (i=0;i<N;i++)  
            {  
                for (j=0;j<N;j++)  
                {  
                    for(k=0;k<N;k++)  
                    {  
                        tm1.m[i][j] += (res.m[i][k]*tm.m[k][j])%MOD;  
                        tm1.m[i][j] %= MOD;  
                    }  
                }  
            }  
            res=tm1;  
        }  
        memset(tm1.m,0,sizeof(tm1.m));  
        for (i=0;i<N;i++)  
        {  
            for (j=0;j<N;j++)  
            {  
            for(k=0;k<N;k++)  
                {  
                    tm1.m[i][j] += (tm.m[i][k]*tm.m[k][j])%MOD;  
                    tm1.m[i][j] %= MOD;  
                }  
            }  
        }  
        tm=tm1;  
        n>>=1;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日