Queuing

Queues and Priority Queues are data structures which are known to most computer scientists. The Queue occurs often in our daily life. There are many people lined up at the lunch time.

  Now we define that ‘f’ is short for female and ‘m’ is short for male. If the queue’s length is L, then there are 2 ^L numbers of queues. For example, if L = 2, then they are ff, mm, fm, mf . If there exists a subqueue as fmf or fff, we call it O-queue else it is a E-queue.
Your task is to calculate the number of E-queues mod M with length L by writing a program.

题意：

给一个队列，每位上放一个f或者m，不能出现fff或fmf，求长度位l的队列的总数，对m取模。

思路：

令f（n）为长度位n时的种数，n位为m时都可以，即f（n-1）。当n位为f时，末尾3位有4种情况：fff，fmf，mmf，mff。前两种不符，当后3位为mmf时，后3位没有限制，即f（n-3），当后3位为mff时，fmff不行，因此后四位只能是mmff，即f（n-4）。

由此得到递推公式f（n）=f（n-1）+f（n-3）+f（n-4）

由于l较大，直接递推会超时，因此想到矩阵快速幂。

#include<iostream> 
#include<stdio.h> 
#include<math.h> 
#include<string.h> 
#include<vector> 
#include<queue> 
#include<map> 
#include<stack> 
#include<queue> 
#include<algorithm> 
using namespace std; 
struct mat
{
	int mm[4][4];
};int n,m;
mat muti(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]=(c.mm[i][j]+a.mm[i][k]*b.mm[k][j])%m;
	return c;
}
int fun(int x)
{
	mat ans,a;
	memset(a.mm,0,sizeof(a.mm));
	memset(ans.mm,0,sizeof(ans.mm));
	for(int i=0;i<4;i++)
		for(int j=0;j<4;j++)
			if(i==j)
				ans.mm[i][j]=1;
	a.mm[0][0]=a.mm[0][2]=a.mm[0][3]=a.mm[1][0]=a.mm[2][1]=a.mm[3][2]=1;//初始化
	while(x>0)//快速幂
	{
		if(x&1)
			ans=muti(ans,a);
		a=muti(a,a);
		x>>=1;
	}
	return (ans.mm[0][0]*9+ans.mm[0][1]*6+ans.mm[0][2]*4+ans.mm[0][3]*2)%m;
}
int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
	
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n==0)printf("0n");
		if(n==1)printf("%dn",2%m);
		if(n==2)printf("%dn",4%m);
		if(n==3)printf("%dn",6%m);
		if(n==4)printf("%dn",9%m);
		if(n>4)
		printf("%dn",fun(n-4));
	}
    return 0;
}

最后

以上就是酷炫菠萝为你收集整理的hdu 2604(矩阵快速幂)Queuing的全部内容，希望文章能够帮你解决hdu 2604(矩阵快速幂)Queuing所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。