hdu 2604 Queuing(矩阵乘法+递推)

69 阅读 0 评论 46 点赞

我是靠谱客的博主调皮蛋挞，最近开发中收集的这篇文章主要介绍hdu 2604 Queuing(矩阵乘法+递推)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目分析：参考：http://qianmacao.blog.163.com/blog/static/203397180201212204149550/

找規律 + 矩陣乘法

設f(n)為字符串為n時符合條件的字符串個數。

以字符串最後一個字符為分界點，當最後一個字符為m時前n-1個字符沒有限制，即為f(n-1)；

當最後一個字符為f時就必須去除最後3個字符是fmf和fff的情況，此時最後三個字符可能為mmf和mff，

當後三個字符為mmf時，前n-3個字符沒有限制，即為f(n-3)；

但是當後三個自負為mff時，後四個字符必須為mmff時前n-4個字符無限制，即為f(n-4)。

這樣就討論完了字符串的構成情況了，得出結論為：f(n) = f(n-1) + f(n-3) + f(n-4).

f(0)=0, f(1)=2, f(2)=4, f(3)=6, f(4)=9;

代码：

#include<iostream>
#include<cstdio>
using namespace std;
struct node 
{
	int matrix[5][5];
}ma,e;
int m;
node operator * (node x,node y)
{
	node temp;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
		{
			temp.matrix[i][j]=0;
			for(int k=1;k<=4;k++)
			{
				temp.matrix[i][j]+=(x.matrix[i][k]*y.matrix[k][j])%m;
			}
			temp.matrix[i][j]%=m;
		}
	return temp;
}
node operator ^(node a,int k)
{
	node ans=e,p=a;
	while(k)
	{
		if(k%2==1)//if(k&1)
		{
		     ans=ans*p;
		}
		k=k/2;
		p=p*p;
	}
	return ans;
}
int pow_mod(int a,int k)
{
	if(k==0)
		return 1;
	if(k==1)
		return a%m;
	else
	{
		int temp=pow_mod(a,k/2);
		if(k&1)
		{
			return (temp*temp*a)%m;
		}
		else
		{
			return (temp*temp)%m;
		}
	}
}
int main()
{
	int k;
	for(int i=1;i<=4;i++)
		for(int j=1;j<=4;j++)
		{
			if(i==j)
				e.matrix[i][j]=1;
			else
				e.matrix[i][j]=0;
		}
	memset(ma.matrix,0,sizeof(ma.matrix));
	ma.matrix[1][1]=ma.matrix[1][3]=ma.matrix[1][4]=1;
	ma.matrix[2][1]=ma.matrix[3][2]=ma.matrix[4][3]=1;
	while(scanf("%d %d",&k,&m)!=EOF)
	{
		int ans;
		if(0==k)
			ans=0;
		else if(1==k)
			ans=2%m;
		else if(2==k)
			ans=4%m;
		else if(3==k)
			ans=6%m;
		else if(4==k)
			ans=9%m;
		else
		{
			node t=ma^(k-4);
			ans=(t.matrix[1][1]*9+t.matrix[1][2]*6+t.matrix[1][3]*4+t.matrix[1][4]*2)%m;
		}
		printf("%dn",ans);
	}
	system("pause");
	return 0;
}