轉(zhuǎn)載博客：http://blog.csdn.net/hcbbt/article/details/38363353
HDU 2604 Queuing （矩陣快速冪）

ACM

題目地址：HDU 2604 Queuing

題意：
n個(gè)人排隊(duì)，f表示女，m表示男，包含子串‘fmf’和‘fff’的序列為O隊(duì)列，否則為E隊(duì)列，有多少個(gè)序列為E隊(duì)列。

分析：
矩陣快速冪入門題。
下面引用巨巨解釋：

用f(n)表示n個(gè)人滿足條件的結(jié)果，那么如果最后一個(gè)人是m的話，那么前n-1個(gè)滿足條件即可，就是f(n-1)； 如果最后一個(gè)是f那么這個(gè)還無法推出結(jié)果，那么往前再考慮一位：那么后三位可能是：mmf, fmf, mff, fff，其中fff和fmf不滿足題意所以我們不考慮，但是如果是 mmf的話那么前n-3可以找滿足條件的即：f(n-3)；如果是mff的話，再往前考慮一位的話只有mmff滿足條件即：f(n-4) 所以f(n)=f(n-1)+f(n-3)+f(n-4)，遞推會(huì)跪，可用矩陣快速冪 構(gòu)造一個(gè)矩陣： pic

矩陣快速冪和普通的快速冪原理是一樣的，如果不懂可以先去補(bǔ)補(bǔ)快速冪。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int l,m; struct mat {long long mm[4][4]; }; mat operator*(mat a,mat b) {mat c;memset(c.mm,0,sizeof(c.mm));for(int i=0;i<4;i++)for(int j=0;j<4;j++)for(int k=0;k<4;k++){c.mm[i][j]+=a.mm[i][k]*b.mm[k][j];c.mm[i][j]%=m;}return c; } void pow() {mat res,ans;memset(res.mm,0,sizeof(res.mm));memset(ans.mm,0,sizeof(ans.mm));ans.mm[0][0]=9;ans.mm[0][1]=6;ans.mm[0][2]=4;ans.mm[0][3]=2;for(int i=0;i<3;i++)res.mm[i][i+1]=1;for(int i=0;i<4;i++)res.mm[i][0]=1;res.mm[1][0]=0;l-=4;while(l){if(l%2==1)ans=ans*res;res=res*res;l/=2;}printf("%lld\n",ans.mm[0][0]%m); } int main() {while(~scanf("%d%d",&l,&m)){if(l==1){printf("%d\n",2%m);}else if(l==2){printf("%d\n",4%m);}else if(l==3){printf("%d\n",6%m);}else if(l==4){printf("%d\n",9%m);}else{pow();}} }

總結(jié)

以上是生活随笔為你收集整理的HDU2604的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。