这篇博客是从旧博客 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