Queuing
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2586 Accepted Submission(s): 1210
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 2L 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.
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 2L 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 6) and M.
Output
Output K mod M(1 <= M <= 30) where K is the number of E-queues with length L.
Sample Input
3 8
4 7
4 8
Sample Output
6
2
1
Author
WhereIsHeroFrom
题意:
给出 L 和 M,代表 L 长度的队伍,f 代表女生,m 代表有男生,存在 fmf 或者 fff 的队伍叫 O - queue,没有叫做 E - queue,求出 L 长度序列的队伍有多少种 E - queue 的可能,结果 % M。
思路:
矩阵快速幂。
设 ai 为以 fm 为后缀的包含序列的种数;
bi 为以 ff 为后缀的包含序列的种数;
ci 为以 mm 为后缀的包含序列的种数;
di 为以 mf 为后缀的包含序列的种数;
ei 为以 fm 为后缀的不包含序列的种数;
fi 为以 ff 为后缀的不包含序列的种数;
gi 为以 mm 为后缀的不包含序列的种数;
hi 为以 mf 为后缀的不包含序列的种数。
所以:
ai+1 = bi + ci; bi+1 = bi + ci + di ; ci+1 = ai + di + ei ; di+1 = ai + di;
ei+1 = fi + gi; fi+1 = gi ;gi+1 = hi ; hi = ei + hi
所以可以得出矩阵:
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef vector<int> vec; typedef vector<vec> mat; mat mul (mat a, mat b, int mod) { mat c(a.size(), vec(b[0].size())); for (int i = 0; i < a.size(); ++i) { for (int j = 0; j < b[0].size(); ++j) { for (int k = 0; k < b.size(); ++k) { c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod; } } } return c; } mat pow (mat a, int n, int mod) { mat b(a.size(), vec(a[0].size())); for (int i = 0; i < a.size(); ++i) { b[i][i] = 1; } while(n > 0) { if (n & 1) b = mul(b, a, mod); a = mul(a, a, mod); n >>= 1; } return b; } int main() { int l, m; while (~scanf("%d%d", &l, &m)) { mat a(8, vec(8)); a[0][1] = 1, a[0][2] = 1, a[1][1] = 1; a[1][2] = 1, a[1][5] = 1, a[2][0] = 1; a[2][3] = 1, a[2][4] = 1, a[3][0] = 1; a[3][3] = 1, a[4][5] = 1, a[4][6] = 1; a[5][6] = 1; a[6][7] = 1, a[7][4] = 1; a[7][7] = 1; mat b(8, vec(1)); b[1][0] = 1, b[2][0] = 1, b[4][0] = 2; b[5][0] = 1, b[6][0] = 1, b[7][0] = 2; if (l > 3) { a = pow(a, l - 3, m); b = mul(a, b, m); int sum = 0; for (int i = 4; i < 8; ++i) { sum = (sum + b[i][0]) % m; } printf("%d\n", sum % m); } else if (l == 3) printf("%d\n", 6 % m); else printf("0\n"); } return 0; }
相关推荐
Queuing analysis is one of the most important tools for those involved with computer and network analysis. It can be used to provide approximate answers to a host of questions, such as: · What ...
讲排队论的经典教材 Chapman.and.Hall.CRC. Performance.Analysis.of.Queuing.and.Computer.Networks.Jun.2008
Performance Analysis of Queuing and Computer Networks 英文版 超清晰 非扫描 有完整书签
message_queuing_for_business_integration
PPT, 罗格斯大学的英文课件,42页。还行,基础理论。
HTB linux queuing discipline manual--userguide HTB 流量控制手册——用户指导 讲述linux htb调度算法和原理,原书的中文版,推荐
java连接MSMQ的类库,找了好久的东西
对于SATA2.0协议中的NCQ技术的介绍,是比较权威的一篇文章。
排队理论的英文题目,用于测试排队这一科目的半学期水平。
Laravel开发-queuing 排队提供排队性能提高幅度4.2
This code is for message queuing using c#
基于排队网络认知体系的驾驶员车辆跟驰模型研究,毕路拯,Liu Yili ,车辆跟驰控制是一种常见的驾驶活动。在认知体系框架下建模驾驶员的车辆跟驰控制有助于和驾驶相关的人因研究。 排队网络认知体系�
this is about queuing theory. For simulating different type of queuing including M/M/1,M/M/C
Queuing_system_simulator
一本关于网络分析的书,主要采用网络微积分的数学工具。
sample question queueing theory
Use of Action Queuing in SAP MII.pdf
通过Redis分布式缓存数据库或RabbitMQ实现消息队列(MessageQueuing)
基于Message Queuing的推拉技术在车间任务分配中的实现,余斌,王纯贤,分析了“拉取”与“推送”两种信息服务模式,并详细介绍了Message Queuing消息传送与接收。提出一种基于Message Queuing的推拉技术结合的车
e-business_integration_using_advanced_queuing