233 matrix

题源:Problem - 5015 (hdu.edu.cn)

题意

     给出第一行的规律 a00,a01,a02, , , , a0m = 0,233,2333,23333 ,,,,

     第一列的数input给出 a00, a10, a20 , a30, ,,, an0 = 0, a1,a2 ,a3,a4,,,,an

     第 aij 为 ai-1,j + ai, j-1 , 求 an,m

规律总结

    把矩阵看作一列一列的找规律

    可以发现第 j 列 可以很容易通过第 j-1 列 相加推导得出, 除去第一行有些不对称

    第一行分别为 0,233,2333,23333 ,可以将第一个改为23,则 ai= ai-1*10 +3 。 

一般快速幂

    当计算 a ^n 时,例如 12345 ^255  ,需要进行 255次乘法,时间复杂度 O(n)

   可以将时间复杂度降到 O(log n ) 

    方法是 255 = 111111112

    可以将 12345^255 = 12345 ^(2^7*1+2^6*1+ 2*5*1+ + 2^0*1)

                                   = 12345^(2^7) * 12345* (2^6)* *** 12345^(2^0)

     时间复杂度降为项为1的个数和最高次幂的位数 ,8^7  时间复杂度  O(log n*log n)

给出算法

int QuickPower(int a,int n){
    //return a^n
    int ret = 1;
    int tem = a;
    while(n){
        if(n&1)
            ret *= tem;
        tem *= tem;
        n>>=1;
    }
    return ret;
}

 

 

矩阵快速幕

   

将乘法变成矩阵乘法,给出模板。

233 matrix

 

给出算法模板:

    

const int N = 100;
struct Mat
{
    int m[N][N];
} ans, res; //res result

Mat Mul(Mat a, Mat b,int n){
    //定义矩阵的乘法
    Mat ret;
    for (int i = 0; i < n;i++)
        for (int j = 0; j < n; j++)
            ret.m[i][j] = 0;

    for (int i = 0; i < n;i++)
        for (int j = 0; j < n;j++)
            for (int k = 0; k < n;k++)
                ret.m[i][j] += a.m[i][k] * b.m[k][j];
    return ret;
}

void QuickPower(int N,int n){
    // 求 n阶方阵 的 N次幂
    for (int i = 0; i < n;i++)
        for (int j = 0; j < n;j++)
            ans.m[i][j] = 0;
    while(N){
        if(N&1)
            ans = Mul(ans, res,n);
        N >>= 1;
        res = Mul(res, res,n);
    }

}

 

上一篇:locate 快速查找文件位置


下一篇:Centos7安装Hadoop