📄 十个利用矩阵乘法解决的经典题目.htm
字号:
000。<BR> 下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。<BR> 题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3
*
log(n)，AC了。<BR><BR> 最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：<BR> Matrix67原创，转贴请注明出处。<BR><BR>
<DIV class=UBBPanel>
<DIV class=UBBTitle><IMG style="MARGIN: 0px 2px -3px 0px" alt=程序代码
src="十个利用矩阵乘法解决的经典题目.files/quote.gif"> 程序代码</DIV>
<DIV class=UBBContent><PRE><CODE class=cpp>#include <cstdio><BR>#define SIZE (1<<m)<BR>#define MAX_SIZE 32<BR>using namespace std;<BR><BR>class CMatrix<BR>{<BR> public:<BR> long element[MAX_SIZE][MAX_SIZE];<BR> void setSize(int);<BR> void setModulo(int);<BR> CMatrix operator* (CMatrix);<BR> CMatrix power(int);<BR> private:<BR> int size;<BR> long modulo;<BR>};<BR><BR>void CMatrix::setSize(int a)<BR>{<BR> for (int i=0; i<a; i++)<BR> for (int j=0; j<a; j++)<BR> element[i][j]=0;<BR> size = a;<BR>}<BR><BR>void CMatrix::setModulo(int a)<BR>{<BR> modulo = a;<BR>}<BR><BR>CMatrix CMatrix::operator* (CMatrix param)<BR>{<BR> CMatrix product;<BR> product.setSize(size);<BR> product.setModulo(modulo);<BR> for (int i=0; i<size; i++)<BR> for (int j=0; j<size; j++)<BR> for (int k=0; k<size; k++)<BR> {<BR> product.element[i][j]+=element[i][k]*param.element[k][j];<BR> product.element[i][j]%=modulo;<BR> }<BR><BR> return product;<BR>}<BR><BR>CMatrix CMatrix::power(int exp)<BR>{<BR> CMatrix tmp = (*this) * (*this);<BR> if (exp==1) return *this;<BR> else if (exp & 1) return tmp.power(exp/2) * (*this);<BR> else return tmp.power(exp/2);<BR>}<BR><BR><BR>int main()<BR>{<BR> const int validSet[]={0,3,6,12,15,24,27,30};<BR> long n, m, p;<BR> CMatrix unit;<BR> <BR> scanf("%d%d%d", &n, &m, &p);<BR> unit.setSize(SIZE);<BR> for(int i=0; i<SIZE; i++)<BR> for(int j=0; j<SIZE; j++)<BR> if( ((~i)&j) == ((~i)&(SIZE-1)) )<BR> {<BR> bool isValid=false;<BR> for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];<BR> unit.element[i][j]=isValid;<BR> }<BR><BR> unit.setModulo(p);<BR> printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );<BR> return 0;<BR>}</CODE></PRE></DIV></DIV><BR><BR><BR></DIV>
<SCRIPT type=text/javascript><!--google_ad_client = "pub-8918918108662869";google_ad_width = 728;google_ad_height = 90;google_ad_format = "728x90_as";google_ad_type = "text_image";google_ad_channel = "";google_color_border = "CCCCCC";google_color_bg = "F3F3F3";google_color_link = "6060FF";google_color_text = "292929";google_color_url = "000000";//--></SCRIPT>
<SCRIPT src="十个利用矩阵乘法解决的经典题目.files/show_ads.js" type=text/javascript></SCRIPT>
<DIV class=Content-body><IMG style="MARGIN: 0px 2px -4px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_trackback.gif"><STRONG>引用通告地址:</STRONG>
http://www.matrix67.com/blog/trackback.asp?tbID=JOFQLPG8&key=JOKOJQDPMMDQM8<BR><IMG
style="MARGIN: 4px 2px -4px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/tag.gif"><STRONG>Tags:</STRONG> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E7%9F%A9%E9%98%B5">矩阵</A><A
style="DISPLAY: none" href="http://technorati.com/tag/矩阵" rel=tag>矩阵</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E8%B6%A3%E9%A2%98">趣题</A><A
style="DISPLAY: none" href="http://technorati.com/tag/趣题" rel=tag>趣题</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E7%AE%97%E6%B3%95">算法</A><A
style="DISPLAY: none" href="http://technorati.com/tag/算法" rel=tag>算法</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E5%88%86%E6%B2%BB">分治</A><A
style="DISPLAY: none" href="http://technorati.com/tag/分治" rel=tag>分治</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E4%BD%8D%E8%BF%90%E7%AE%97">位运算</A><A
style="DISPLAY: none" href="http://technorati.com/tag/位运算" rel=tag>位运算</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E6%95%B0%E5%88%97">数列</A><A
style="DISPLAY: none" href="http://technorati.com/tag/数列" rel=tag>数列</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E5%9B%BE%E8%AE%BA">图论</A><A
style="DISPLAY: none" href="http://technorati.com/tag/图论" rel=tag>图论</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92">动态规划</A><A
style="DISPLAY: none" href="http://technorati.com/tag/动态规划" rel=tag>动态规划</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=Vijos">Vijos</A><A
style="DISPLAY: none" href="http://technorati.com/tag/Vijos" rel=tag>Vijos</A>
<A href="http://www.matrix67.com/blog/default.asp?tag=POJ">POJ</A><A
style="DISPLAY: none" href="http://technorati.com/tag/POJ" rel=tag>POJ</A> <A
href="http://www.matrix67.com/blog/default.asp?tag=C%E8%AF%AD%E8%A8%80">C语言</A><A
style="DISPLAY: none" href="http://technorati.com/tag/C语言" rel=tag>C语言</A> <BR><!--Add By WBC --><IMG style="MARGIN: 4px 2px -4px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/tag.gif"><STRONG>我猜你可能喜欢:</STRONG><BR>
<DIV class=Content-body id=wbc_tag></DIV><BR><!--End By WBC --></DIV>
<DIV class=Content-bottom>
<DIV class=ContentBLeft></DIV>
<DIV class=ContentBRight></DIV>评论: 8</A> | <A
href="http://www.matrix67.com/blog/trackback.asp?tbID=JOFQLPG8&key=JOKOJQDPMMDQM8"
target=_blank>引用: 0</A> | 查看次数: 2524 </DIV></DIV></DIV><A accessKey=C
href="http://www.matrix67.com/blog/article.asp?id=324#comm_top"
name=comm_top></A>
<DIV class=pageContent>
<DIV class=page style="FLOAT: right">
<UL>
<LI class=pageNumber><STRONG>1</STRONG></LI></UL></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('rmq','commcontent_2654')"
name=comm_2654><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> rmq <SPAN
class=commentinfo>[楼层: 地幔 发表时间: 2008-01-13 04:43 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_2654>啊，太荣幸了，大牛居然贴我blog上的一个小题目
~~<BR>太开心了<BR><BR><SPAN
style="COLOR: red">回复：您牛的blog我每天都上，都是经典题目啊</SPAN></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('晗熙','commcontent_1963')"
name=comm_1963><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> <A
href="http://mycrazy.blogcn.com/" target=_blank><STRONG>晗熙</STRONG></A> <SPAN
class=commentinfo>[楼层: 地壳 发表时间: 2007-11-15 04:36 PM]</SPAN></DIV>
<DIV class=commentcontent
id=commcontent_1963>第九题 超经典<BR>能否写个pascal???<BR></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('hey','commcontent_1705')"
name=comm_1705><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> hey <SPAN
class=commentinfo>[楼层: 地基 发表时间: 2007-10-21 01:56 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_1705>给个建议, 规范 C++ 书写.<BR>#include
<cstdio>, #define, scanf, printf 之类的东西不该出现哦.</DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('Kimm','commcontent_1247')"
name=comm_1247><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> Kimm <SPAN
class=commentinfo>[楼层: 地下室 发表时间: 2007-08-17 10:51 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_1247>经典题目9
能否再解释下<BR>看不是很懂<BR>左边的状态是怎么转移到右边的<BR>111又是怎么转移到011的？</DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A
href="javascript:addQuote('lsylsy2','commcontent_1094')" name=comm_1094><IMG
style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> <A
href="http://www.matrix67.com/blog/member.asp?action=view&memName=lsylsy2"
target=_blank><STRONG>lsylsy2</STRONG></A> <SPAN class=commentinfo>[楼层: 地板 发表时间:
2007-08-10 08:08 PM]</SPAN></DIV>
<DIV class=commentcontent id=commcontent_1094>矩阵=matrix</DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A href="javascript:addQuote('yiyi','commcontent_1020')"
name=comm_1020><IMG style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> <A
href="http://www.whorevideos.com/" target=_blank><STRONG>yiyi</STRONG></A> <SPAN
class=commentinfo>[楼层: 地毯 发表时间: 2007-08-05 08:31 PM]</SPAN></DIV>
<DIV class=commentcontent
id=commcontent_1020>第6题的那个用矩阵乘法求第n个Fibonacci数的算法很感兴趣，可看的还是不大明白，能说的再详细一点吗？<BR><BR><SPAN
style="COLOR: red">回复：usera.imagecave.com/matrix67/fib_using_matrix.GIF</SPAN></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A
href="javascript:addQuote('windywinter','commcontent_1005')" name=comm_1005><IMG
style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> <A
href="http://turingdream.com/" target=_blank><STRONG>windywinter</STRONG></A>
<SPAN class=commentinfo>[楼层: 板凳 发表时间: 2007-08-04 08:43 AM]</SPAN></DIV>
<DIV class=commentcontent
id=commcontent_1005>另外，matrix67大牛为什么不写一个矩阵快速乘法呢？这个一直弄不明白怎么做。<BR><BR><SPAN
style="COLOR: red">回复：是不是这个？<BR><A
href="http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/commonalg/misc/strassen/strassen.htm"
target=_blank>http://www.comp.nus.edu.sg/~xujia/mirror/algorithm.myrice.com/algorithm/commonalg/misc/strassen/strassen.htm</A></SPAN></DIV></DIV>
<DIV class=comment>
<DIV class=commenttop><A
href="javascript:addQuote('windywinter','commcontent_1004')" name=comm_1004><IMG
style="MARGIN: 0px 4px -3px 0px" alt=""
src="十个利用矩阵乘法解决的经典题目.files/icon_quote.gif" border=0></A> <A
href="http://turingdream.com/" target=_blank><STRONG>windywinter</STRONG></A>
<SPAN class=commentinfo>[楼层: 沙发 发表时间: 2007-08-04 08:42 AM]</SPAN></DIV>
<DIV class=commentcontent
id=commcontent_1004>重载双目运算符尽量放到类定义的外面，以避免不同编译器的区别。<BR><BR><SPAN
style="COLOR: red">回复：谢谢指点；这方面的东西我还不太熟，过几天来研究</SPAN></DIV></DIV>
<DIV class=pageContent>
<DIV class=page style="FLOAT: right">
<UL>
<LI class=pageNumber><STRONG>1</STRONG></LI></UL></DIV></DIV>
<DIV id=MsgContent style="WIDTH: 94%">
<DIV id=MsgHead>发表评论</DIV>
<DIV id=MsgBody>
<FORM style="MARGIN: 0px" name=frm onsubmit="return CheckPost()"
action=blogcomm.asp method=post>
<TABLE cellSpacing=0 cellPadding=0 width="100%">
<TBODY>
<TR>
<TD align=right width=70><STRONG>昵 称:</STRONG></TD>
<TD
style="PADDING-RIGHT: 3px; PADDING-LEFT: 3px; PADDING-BOTTOM: 3px; PADDING-TOP: 3px"
align=left><INPUT class=userpass maxLength=24 size=18 name=username></TD></TR>
<TR>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -