随笔-72  评论-126  文章-0  trackbacks-0
矩阵运算。。很早的时候就下了一个课件,不过一直没有看,因为不知道什么地方可以用(没看当然不知道了)
前几天做了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=1683
Sn的公式很快就推出来了,用矩阵二分竟然超时。。。
后来经指点是取模次数太多了,经过多次修改,终于过了。。

又一想,当年菜鸟杯一道推推题目知道公式但是。怎么也写不出
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ǎ崽 阅读(2250) 评论(8)  编辑 收藏 引用

评论:
# re: 神奇的matrix运算 2009-03-20 20:46 | future
http://acm.fzu.edu.cn/problem.php?pid=1683
Sn的公式很快就推出来了,。。。。”
我这题用矩阵幂暴力做就TLE掉了,
请问你sn公式是怎么推的!能否告知一下!谢谢~~  回复  更多评论
  
# re: 神奇的matrix运算 2009-03-23 14:00 | shǎ崽
@future


A = [1 1 0 0]
[0 3 2 7]
[0 1 0 0]
[0 0 1 0]

B = [Sn]
[Fn-1]
[Fn-2]
[Fn-3]  回复  更多评论
  
# re: 神奇的matrix运算 2009-04-12 09:19 | ouye
大牛
http://acm.hdu.edu.cn/showproblem.php?pid=2256
这道要巧妙的转化后推公式

后推公式是怎么推得?能否告知,thanks

  回复  更多评论
  
# re: 神奇的matrix运算 2009-04-12 11:51 | matrix
http://acm.hdu.edu.cn/showproblem.php?pid=2276
这道比赛时候看不出是矩阵。。。后来知道了很好做,因为上下相差一行,直接n^2的算法可以代替n^3

大牛, 可以具体解释下吗? 谢  回复  更多评论
  
# re: 神奇的matrix运算 2009-04-13 00:09 | shǎ崽
@matrix


因为上下只相差一位
所以可以用





只算出第一行,然后接下来的根据移位得到

。。。
算了,这里格式不好,我贴到上边去

  回复  更多评论
  
# re: 神奇的matrix运算 2009-04-13 00:12 | shǎ崽
@ouye


num[1] = 10;
num[2] = 98
num[i] = num[i-1]*10 - num[i-2];

然后num[i] - 1就是所求的答案  回复  更多评论
  
# re: 神奇的matrix运算 2009-05-03 14:38 | phoenix
能否提供下关于矩阵运算的课件给我,谢了~  回复  更多评论
  
# re: 神奇的matrix运算 2009-05-08 21:39 | Wpl
牛.......  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理