点击打开题目

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.

  
  

   
   3 8
4 7
4 8
  
  

  
  

   
   6
2
1
  
  

这个题推递推公式又是个大麻烦了。

我们还是考虑最后一位，观察知道如果最后一位是m的话，前面就不用管了，这样的方案数为f（i - 1）。

然后是最后一位是 f 的情况，我们知道，最后一位是 f 时，前面两位只能是mmf、mff。

如果是mmf的话，前面是什么也不用管了，这种的方案数为f（i - 3）。

如果是mff，再前面是只能是m，所以它的方案数为f（i - 4）。

然后把上面的加起来就得到了递推公式：

f（n）= f（n - 1）+ f（n - 3）+ f（n - 4）

然后是矩阵的构造了，

如图：

（突然发现上面最后一个式子有误，后面的应该是（fn  fn-1  fn-2  fn-3））

代码如下：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 4
#define CLR(a,b) memset(a,b,sizeof(a))
int MOD;
struct Matrix
{
	__int64 m[MAX+5][MAX+5];
	int w,h;
}pr,res,ori;
void init()
{
	pr.w = pr.h = 4;		//构造4*4的矩阵
	CLR(pr.m,0);
	for (int i = 1 ; i <= 3 ; i++)
		pr.m[i][i+1] = pr.m[i][1] = 1;
	pr.m[4][1] = 1;
	pr.m[2][1] = 0;
	res.h = 4;		//构造单位矩阵
	res.w = 4;
	CLR(res.m,0);
	for (int i = 1 ; i <= 4 ; i++)
		res.m[i][i] = 1;
}
Matrix Matrix_multiply(Matrix x,Matrix y)
{
	Matrix t;
	t.h = x.h;
	t.w = y.w;
	CLR(t.m,0);
	for (int i = 1 ; i <= x.h ; i++)
	{
		for (int j = 1 ; j <= x.w ; j++)
		{
			if (x.m[i][j] == 0)
				continue;
			for (int k = 1 ; k <= y.w ; k++)
				t.m[i][k] = (t.m[i][k] + x.m[i][j] * y.m[j][k] % MOD) % MOD;
		}
	}
	return t;
}
void Matrix_mod(int n)		//矩阵快速幂 
{
	while (n)
	{
		if (n & 1)
			res = Matrix_multiply(res , pr);
		pr = Matrix_multiply(pr , pr);
		n >>= 1;
	}
}
int main()
{
	int n;
	ori.w = 4;
	ori.h = 1;
	ori.m[1][1] = 9;
	ori.m[1][2] = 6;
	ori.m[1][3] = 4;
	ori.m[1][4] = 2;
	while (~scanf ("%d %d",&n,&MOD))
	{
		if (n == 0)
		{
			printf ("0n");
			continue;
		}
		else if (n <= 4)
		{
			printf ("%I64dn",ori.m[1][5-n] % MOD);
			continue;
		}
		init();
		Matrix_mod(n - 4);
		res = Matrix_multiply(ori , res);		//要注意矩阵乘法没有交换律
		printf ("%I64dn",res.m[1][1]);
	}
	return 0;
}

最后

以上就是外向手机为你收集整理的【HDU】2604 - Queuing（递推 & 思维 & 矩阵构造 & 快速幂） Queuing的全部内容，希望文章能够帮你解决【HDU】2604 - Queuing（递推 & 思维 & 矩阵构造 & 快速幂） Queuing所遇到的程序开发问题。

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