HDU 2604 QueuingQueuing

90 阅读 0 评论 60 点赞

我是靠谱客的博主还单身乌龟，这篇文章主要介绍HDU 2604 QueuingQueuing，现在分享给大家，希望可以做个参考。

Queuing

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 690 Accepted Submission(s): 337

Problem Description

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.

Input

Input a length L (0 <= L <= 10 ⁶) and M.

Output

Output K mod M(1 <= M <= 30) where K is the number of E-queues with length L.

Sample Input

复制代码

Sample Output

复制代码

6
2
1
    
    
    
    
    
    
     
     //本题的思想是推出公式，F（N）=F（N-1）+F（N-3）+F（N-4）
//因为假设F（N）为已经是E队列的个数， 那么有3种情况
//就是一，在F（N-1）后加一个M
//二，在F（N-3）后加MMF 
//三，在F（N-4）后加MMFF
//所以得到递推式后即可用 矩阵乘法 解决问题

#include<stdio.h>
struct node
{
    long long num[4][4];
};

node res,tp;
int n,m;

node mut(node a,node b)
{
	node c;
	int i,j,k;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
		{
			c.num[i][j]=0;
			for(k=0;k<4;k++)
				c.num[i][j]+=(a.num[i][k]*b.num[k][j])%m;
			c.num[i][j]%=m;
		}
		return c;
}

node abc(int temp,node p)
{
	tp=p;
	p=res;
	while(temp)
	{
		if(temp&1)
			p=mut(p,tp);
		tp=mut(tp,tp);
		temp>>=1;
	}
	return p;
}

int main()
{
	int i,j;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			res.num[i][j]=(i==j);
	node p;
p.num[0][0]=p.num[0][2]=p.num[0][3]=p.num[1][0]=p.num[2][1]=1;
	p.num[3][2]=1;
	p.num[1][1]=p.num[1][2]=p.num[1][3]=p.num[2][0]=0;
	p.num[0][1]=p.num[2][2]=p.num[2][3]=p.num[3][0]=0;
	p.num[3][1]=p.num[3][3]=0;
	int a[5]={0,2,4,6,9};
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n<=4)
		{
			printf("%d/n",a[n]%m);
			continue;
		}
		node k;
		k=abc(n-4,p);
		int sum=(k.num[0][0]*9+k.num[0][1]*6+k.num[0][2]*4+k.num[0][3]*2)%m;
		printf("%d/n",sum);
	}
	return 0;
} 
    
    
    
    
    
    
     
     下面的一样
    
    
    
    
     
     #include<stdio.h>
int n,m,l;
long long a[4][4],sum[4][4],hash[4][4];
void find()
{
    int i,j,p,t,k;
	for(p=n-4;p>0;)
	{
		if(p&1)
		{
			for(i=0;i<4;i++)
			{
				for(j=0;j<4;j++)
				{
					for(k=0,t=0;k<4;k++)
						t=t+sum[i][k]*hash[k][j];
					a[i][j]=t%m;
				}
			}
			for(i=0;i<4;i++)
				for(j=0;j<4;j++)
					hash[i][j]=a[i][j];
				p--;
		}
		else 
		{
			for(i=0;i<4;i++)
			{
				for(j=0;j<4;j++)
				{
					for(k=0,t=0;k<4;k++)
						t=t+sum[i][k]*sum[k][j];
					a[i][j]=t%m;
				}
			}
			for(i=0;i<4;i++)
				for(j=0;j<4;j++)
					sum[i][j]=a[i][j];
				p=p>>1;
		}
	}
}
int main()
{
	int i,j;
	int b[5]={0,2,4,6,9};
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n<5)
		{
			printf("%d/n",b[n]%m);
			continue;
		}
		for(i=0;i<4;i++)
			for(j=0;j<4;j++)
				sum[i][j]=hash[i][j]=0;
         for(i=0;i<4;i++)
		    hash[i][i]=1;
	    sum[0][0]=sum[0][2]=sum[0][3]=1;
	    sum[1][0]=sum[2][1]=sum[3][2]=1;
			find();
			l=a[0][0]*9+a[0][1]*6+a[0][2]*4+a[0][3]*2;
			l=l%m;	
		printf("%d/n",l);
	}
	return 0;
} 
    
    
    
    
    
    
     
     还可以用打表法
    
    
    
    
     
     /************************************************************************
   
前四位我们可以算出d[1]=2,d[2]=4,d[3]=6,d[4]=9.

我们可以这样想：一个合法串可以由两个较短的合法串组成

就以d[n]为例：(注意不能重复)

1、n-1个字符的时候: +m

2、n-2: 只能+mm，会和n-1重复,所以不考虑n-2

3、n-3: +mmf

4、n-4: +mmff

5、n-5: 如果是+mmffm，会与n-1重复,+mmmff会与n-4重复,+mmmmf会与n-3重复(不考虑)

所以就考虑n-1,n-3,n-4，DP等式就出来了:dp[n]=dp[n-1]+dp[n-3]+dp[n-4]

n<10^6  m<=30   用打表可以做

[刚刚开始直接用int敲的代码，果断MLE了。。。改成char试试 - -就过了]

************************************************************************/

#include <stdio.h>
#define N 1000001
#define M 30

char node[N][M];

void init()
{
	int i,j;
	for(i=1;i<=M;i++)
	{
		node[1][i]=2%i;
		node[2][i]=4%i;
		node[3][i]=6%i;
		node[4][i]=9%i;
		for (j=5;j<=N;j++)
		{
			node[j][i]=(node[j-1][i]+node[j-3][i]+node[j-4][i])%i;
		}
	}
}

int main()
{
	init();
	int n,m;
	while (~scanf("%d%d",&n,&m))
	{
		printf("%d/n",node[n][m]);
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237

     
     6
2
1
    
    
    
    
    
    
     
     //本题的思想是推出公式，F（N）=F（N-1）+F（N-3）+F（N-4）
//因为假设F（N）为已经是E队列的个数， 那么有3种情况
//就是一，在F（N-1）后加一个M
//二，在F（N-3）后加MMF 
//三，在F（N-4）后加MMFF
//所以得到递推式后即可用 矩阵乘法 解决问题

#include<stdio.h>
struct node
{
    long long num[4][4];
};

node res,tp;
int n,m;

node mut(node a,node b)
{
	node c;
	int i,j,k;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
		{
			c.num[i][j]=0;
			for(k=0;k<4;k++)
				c.num[i][j]+=(a.num[i][k]*b.num[k][j])%m;
			c.num[i][j]%=m;
		}
		return c;
}

node abc(int temp,node p)
{
	tp=p;
	p=res;
	while(temp)
	{
		if(temp&1)
			p=mut(p,tp);
		tp=mut(tp,tp);
		temp>>=1;
	}
	return p;
}

int main()
{
	int i,j;
	for(i=0;i<4;i++)
		for(j=0;j<4;j++)
			res.num[i][j]=(i==j);
	node p;
p.num[0][0]=p.num[0][2]=p.num[0][3]=p.num[1][0]=p.num[2][1]=1;
	p.num[3][2]=1;
	p.num[1][1]=p.num[1][2]=p.num[1][3]=p.num[2][0]=0;
	p.num[0][1]=p.num[2][2]=p.num[2][3]=p.num[3][0]=0;
	p.num[3][1]=p.num[3][3]=0;
	int a[5]={0,2,4,6,9};
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n<=4)
		{
			printf("%d/n",a[n]%m);
			continue;
		}
		node k;
		k=abc(n-4,p);
		int sum=(k.num[0][0]*9+k.num[0][1]*6+k.num[0][2]*4+k.num[0][3]*2)%m;
		printf("%d/n",sum);
	}
	return 0;
} 
    
    
    
    
    
    
     
     下面的一样
    
    
    
    
     
     #include<stdio.h>
int n,m,l;
long long a[4][4],sum[4][4],hash[4][4];
void find()
{
    int i,j,p,t,k;
	for(p=n-4;p>0;)
	{
		if(p&1)
		{
			for(i=0;i<4;i++)
			{
				for(j=0;j<4;j++)
				{
					for(k=0,t=0;k<4;k++)
						t=t+sum[i][k]*hash[k][j];
					a[i][j]=t%m;
				}
			}
			for(i=0;i<4;i++)
				for(j=0;j<4;j++)
					hash[i][j]=a[i][j];
				p--;
		}
		else 
		{
			for(i=0;i<4;i++)
			{
				for(j=0;j<4;j++)
				{
					for(k=0,t=0;k<4;k++)
						t=t+sum[i][k]*sum[k][j];
					a[i][j]=t%m;
				}
			}
			for(i=0;i<4;i++)
				for(j=0;j<4;j++)
					sum[i][j]=a[i][j];
				p=p>>1;
		}
	}
}
int main()
{
	int i,j;
	int b[5]={0,2,4,6,9};
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		if(n<5)
		{
			printf("%d/n",b[n]%m);
			continue;
		}
		for(i=0;i<4;i++)
			for(j=0;j<4;j++)
				sum[i][j]=hash[i][j]=0;
         for(i=0;i<4;i++)
		    hash[i][i]=1;
	    sum[0][0]=sum[0][2]=sum[0][3]=1;
	    sum[1][0]=sum[2][1]=sum[3][2]=1;
			find();
			l=a[0][0]*9+a[0][1]*6+a[0][2]*4+a[0][3]*2;
			l=l%m;	
		printf("%d/n",l);
	}
	return 0;
} 
    
    
    
    
    
    
     
     还可以用打表法
    
    
    
    
     
     /************************************************************************
   
前四位我们可以算出d[1]=2,d[2]=4,d[3]=6,d[4]=9.

我们可以这样想：一个合法串可以由两个较短的合法串组成

就以d[n]为例：(注意不能重复)

1、n-1个字符的时候: +m

2、n-2: 只能+mm，会和n-1重复,所以不考虑n-2

3、n-3: +mmf

4、n-4: +mmff

5、n-5: 如果是+mmffm，会与n-1重复,+mmmff会与n-4重复,+mmmmf会与n-3重复(不考虑)

所以就考虑n-1,n-3,n-4，DP等式就出来了:dp[n]=dp[n-1]+dp[n-3]+dp[n-4]

n<10^6  m<=30   用打表可以做  

[刚刚开始直接用int敲的代码，果断MLE了。。。改成char试试 - -就过了]

************************************************************************/

#include <stdio.h>
#define N 1000001
#define M 30

char node[N][M];

void init()
{
	int i,j;
	for(i=1;i<=M;i++)
	{
		node[1][i]=2%i;
		node[2][i]=4%i;
		node[3][i]=6%i;
		node[4][i]=9%i;
		for (j=5;j<=N;j++)
		{
			node[j][i]=(node[j-1][i]+node[j-3][i]+node[j-4][i])%i;
		}
	}
}

int main()
{
	init();
	int n,m;
	while (~scanf("%d%d",&n,&m))
	{
		printf("%d/n",node[n][m]);
	}
	return 0;
}