矩陣運(yùn)算。。很早的時(shí)候就下了一個(gè)課件，不過一直沒有看，因?yàn)椴恢朗裁吹胤娇梢杂茫]看當(dāng)然不知道了）
前幾天做了FOJ的月賽，有一道遞推的題
賽后問了紀(jì)哥知道是矩陣的題目
補(bǔ)習(xí)了一下，看了那個(gè)資料
發(fā)現(xiàn)原來這么簡(jiǎn)單，推推題原來都可以這樣做。。
在HDOJ練習(xí)了幾道題目
http://acm.hdu.edu.cn/showproblem.php?pid=1575這道是赤裸裸的矩陣二分
http://acm.hdu.edu.cn/showproblem.php?pid=2256
這道要巧妙的轉(zhuǎn)化后推公式
再去解決FOJ那題。
http://acm.fzu.edu.cn/problem.php?pid=1683Sn的公式很快就推出來了，用矩陣二分竟然超時(shí)。。。
后來經(jīng)指點(diǎn)是取模次數(shù)太多了，經(jīng)過多次修改，終于過了。。
又一想，當(dāng)年菜鳥杯一道推推題目知道公式但是。怎么也寫不出
http://acm.hdu.edu.cn/showproblem.php?pid=2604現(xiàn)在知道矩陣后回去秒殺了，呵呵，開心。。。
http://acm.hdu.edu.cn/showproblem.php?pid=1757這道也是赤裸裸的矩陣
http://acm.hdu.edu.cn/showproblem.php?pid=1588這題目比較惡心，不經(jīng)init矩陣要自己推
連右邊的數(shù)字都要自己推。。。推了一個(gè)晚上。。。結(jié)果效率還不是最高的，15MS
http://acm.hdu.edu.cn/showproblem.php?pid=2276這道比賽時(shí)候看不出是矩陣。。。后來知道了很好做，因?yàn)樯舷孪嗖钜恍校苯觧^2的算法可以代替n^3，爽阿
http://acm.fzu.edu.cn/problem.php?pid=1692還有這道，也是n^2的代替n^3防止超時(shí)
//用n^2代替n^3的方法如下:
//因?yàn)槭翘厥饩仃嚕撼跏季仃嚿舷轮幌嗖钜涣?br>//所以可以計(jì)算第一行然后通過移位來得到全部矩陣
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杯過的最少的竟然也是用到矩陣，賽后看結(jié)題報(bào)告才知道，神奇
分享一下我的矩陣模板吧
struct Mat{
int matrix[4][4];
}init,unit;
int mod;
Mat Mul(Mat a,Mat b)//據(jù)說傳結(jié)構(gòu)體比傳數(shù)組快
{
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ǎ崽 閱讀(2293)
評(píng)論(8) 編輯 收藏 引用