矩陣運算。。很早的時候就下了一個課件，不過一直沒有看，因為不知道什么地方可以用（沒看當然不知道了）
前幾天做了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ǎ崽 閱讀(2324)
評論(8) 編輯 收藏 引用