HDU/HDOJ 1575 Tr A（二分法求矩阵的幂）

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1575

说实话，基本还没做过矩阵的题目，以前偶尔碰到一个，也是水题，直接暴力就行，但是这题的幂太大了，暴力明显不行，orz，百度了下，用二分法求矩阵的幂。

分析：

比如矩阵A, A的n次方A^n ,

当n为偶数时，A^n= A^(n/2 + n/2) = A^(n/2) * A^(n/2)，

当n为奇数时，A^n= A^(n/2 + n/2 + 1) = A^(n/2) * A^(n/2) * A，

所以可以考虑用二分法。

以下是递归的描述：

Matrix POW(Matrix t, int k)
{
    if( k == 1 )
        return t;
    Matrix t1 = POW( t, k/2 );
    t1 = t1*t1;
    if( k & 1 )
        return t1 * t;
    else
        return t1;
}

当然，递归的效率不高，直接换成非递归的形式：

/**
 * HDOJ 1575
 * 二分法求矩阵的幂
 * Date: 2011.11.22
 */

#include 
using namespace std;

int T;
int n, k;

typedef struct Matrix{
    int ma[15][15];
}Matrix;

Matrix A;   // 矩阵A
Matrix B;   // 保存最后的结果
Matrix unit;// 单位矩阵，用于在下面的fun函数中
const int MOD = 9973;

// 两个矩阵相乘
Matrix Mul(Matrix m1, Matrix m2)
{
    Matrix c;
    for(int i=0; i 1)
    {
        if(num & 1)  // 为奇数时，则减一
        {
            --num;
            un = Mul(in, un);   // 这里可以体会下为何un要被设置成单位矩阵
        }
        else
        {
            num >>= 1;
            in = Mul(in, in);

        }
    }
    B = Mul(in, un);
}


int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T;);
    while(T--)
    {
        scanf("%d %d", &n;, &k;);
        for(int i=0; i<n; ++i)
            for(int j=0; j<n; ++j)
            {
                scanf("%d", &A.ma[i][j]);
                B.ma[i][j] = 0;
                unit.ma[i][j] = (i==j);
            }

        fun(k);
        int ans = 0;
        for(int i=0; i<n; ++i)
            ans += B.ma[i][i];

        printf("%d\n", ans%MOD);
    }
}

参考了：http://www.cnblogs.com/jian1573/archive/2011/08/16/2141465.html