HDU 2604 Queuing (递推+矩阵快速幂)

HDU 2604 Queuing (递推+矩阵快速幂)

【题目链接】：​​click here~~​​

【题目大意】：

n个人排队，f表示女，m表示男，包含子串‘fmf’和‘fff’的序列为O队列，否则为E队列，有多少个序列为E队列。

【思路】：

用f(n)表示n个人满足条件的结果，那么如果最后一个人是m的话，那么前n-1个满足条件即可，就是f(n-1)； 如果最后一个是f那么这个还无法推出结果，那么往前再考虑一位：那么后三位可能是：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)，递推会跪，可用矩阵快速幂 构造一个矩阵：

来图一张：

代码：

#includeusing namespace std;typedef long long LL;const int siz=4;int k,mod;struct mut{ int mat[4][4]; // size of matric mut() { memset(mat,0,sizeof(mat)); } void init(int v) { for(int i=0; i<=4; ++i) mat[i][i]=v; }};mut operator * (mut a,mut b){ mut c; for(int i=0; i<4; ++i) { for(int j=0; j<4; ++j) { c.mat[i][j]=0; for(int k=0; k<4; ++k) { c.mat[i][j]+=(a.mat[i][k]*b.mat[k][j])%mod; c.mat[i][j]%=mod; } } } return c;}mut operator ^(mut a,LL n){ mut c; c.init(1); while(n) { if(n&1) c=a*c; a=a*a; n>>=1; } return c;}int main(){ mut a,b,c; a.mat[0][0]=9; a.mat[1][0]=6; a.mat[2][0]=4; a.mat[3][0]=2; b.init(0); b.mat[0][0]=b.mat[0][2]=b.mat[0][3]=b.mat[1][0]=b.mat[2][1]=b.mat[3][2]=1; while(~scanf("%d%d",&k,&mod)) { if(k==0){ puts("0"); } else if(k<=4){ printf("%d\n",a.mat[4-k][0]%mod); } else{ c=b^(k-4); c=c*a; printf("%d\n",c.mat[0][0]%mod); } } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。