矩阵运算。。很早的时候就下了一个课件，不过一直没有看，因为不知道什么地方可以用（没看当然不知道了）
前几天做了FOJ的月赛，有一道递推的题
赛后问了纪哥知道是矩阵的题目
补习了一下，看了那个资料
发现原来这么简单，推推题原来都可以这样做。。
在HDOJ练习了几道题目
http://acm.hdu.edu.cn/showproblem.php?pid=1575这道是赤裸裸的矩阵二分
http://acm.hdu.edu.cn/showproblem.php?pid=2256
这道要巧妙的转化后推公式
再去解决FOJ那题。
http://acm.fzu.edu.cn/problem.php?pid=1683Sn的公式很快就推出来了，用矩阵二分竟然超时。。。
后来经指点是取模次数太多了，经过多次修改，终于过了。。
又一想，当年菜鸟杯一道推推题目知道公式但是。怎么也写不出
http://acm.hdu.edu.cn/showproblem.php?pid=2604现在知道矩阵后回去秒杀了，呵呵，开心。。。
http://acm.hdu.edu.cn/showproblem.php?pid=1757这道也是赤裸裸的矩阵
http://acm.hdu.edu.cn/showproblem.php?pid=1588这题目比较恶心，不经init矩阵要自己推
连右边的数字都要自己推。。。推了一个晚上。。。结果效率还不是最高的，15MS
http://acm.hdu.edu.cn/showproblem.php?pid=2276这道比赛时候看不出是矩阵。。。后来知道了很好做，因为上下相差一行，直接n^2的算法可以代替n^3，爽阿
http://acm.fzu.edu.cn/problem.php?pid=1692还有这道，也是n^2的代替n^3防止超时
//用n^2代替n^3的方法如下:
//因为是特殊矩阵：初始矩阵上下只相差一列
//所以可以计算第一行然后通过移位来得到全部矩阵
Matr Mul(Matr a,Matr b)
{
int i,j,k;
Matr c;
for(j=0;j<n;j++)
{
c.num[0][j] = 0;
for(k=0;k<n;k++)
c.num[0][j] += a.num[0][k]*b.num[k][j];
c.num[0][j] &= 1;
}
for(i=1;i<n;i++)
{
c.num[i][0] = c.num[i-1][n-1];
for(j=1;j<n;j++)
c.num[i][j] = c.num[i-1][j-1];
}
return c;
}
http://acm.hdu.edu.cn/showproblem.php?pid=2294这道baidu杯过的最少的竟然也是用到矩阵，赛后看结题报告才知道，神奇
分享一下我的矩阵模板吧
struct Mat{
int matrix[4][4];
}init,unit;
int mod;
Mat Mul(Mat a,Mat b)//据说传结构体比传数组快
{
int i,j,k;
Mat c;
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
c.matrix[i][j] = 0;
for(k=0;k<4;k++)
c.matrix[i][j] += a.matrix[i][k]*b.matrix[k][j];
if(c.matrix[i][j]>=mod)
c.matrix[i][j]%=mod;
}
return c;
}
Mat cal(int l)//l代表幂
{
Mat p,q;
p = unit;
q = init;
while(l!=1)
{
if(l&1)
{
l--;
p = Mul(p,q);
}
else
{
l>>=1;
q = Mul(q,q);
}
}
p = Mul(p,q);
return p;
}
for(i=0;i<4;i++)
for(j=0;j<4;j++)
unit.matrix[i][j] = (i==j);
posted on 2009-03-03 14:17
shǎ崽 阅读(2272)
评论(8) 编辑 收藏 引用