原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=2604
Queuing
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2538 Accepted Submission(s): 1194
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
Source
Recommend
F(n)表示为L=n,时候E序列的数目;
分析:如果长度n的序列中 1)如果最后一个m,那么只要长度为n-1的序列中所有E序列的最后加上m,就可以构成长度为n的E序列(+=F(n-1))。2)如果最后一个是f,那么长度n-1的序列没有能保证如果n-1长度序列为E,再加上f还是E序列的,也不能保证加上f一定是O序列,所以我接着深入!2.1 如果长度n序列中最后两个为mf、ff、貌似都不能保证一定是E或者O序列,我们继续深入!如果长度n序列中最后3个为mmf、fmf、mff、fff,显然fff、fmf一定是O序列!!而mff不能保证一定是E或者O序列,而mmf如果长度n-3的序列是E序列,那么序列后加上mmf也一定是E序列(+=F(n-3)); 对于mff序列,我们继续深入,长度n序列中最后4个为,mmff、fmff 对于fmff一定是O序列,而mmff一定是E序列,那么很显然了(+=F(n-4))
因此可以推出递推公式F(n) = F(n-1) + F(n-3) + F(n-4);
那么很容易想到循环递推;
#include<cstdio> #define MAXN 1000010 int L,M; int F[MAXN]; int main() { F[1] = 2; F[2] = 4; F[3] = 6; F[4] = 9; while(~scanf("%d%d",&L,&M)) { for(int i=5;i<=1000000;i++) F[i] = (F[i-1]+F[i-3]+F[i-4])%M; printf("%d\n",F[L]%M); } }我会告诉你OJ上的结果,
Run ID | Submit Time | Judge Status | Pro.ID | Exe.Time | Exe.Memory | Code Len. | Language |
11164180 | 2014-07-24 10:45:23 | Time Limit Exceeded | 2604 | 5000MS | 4104K | 293 B | G++ |
其实对于这种超时,很容易想到用矩阵快速幂
构造矩阵
/* 1,0,1,1 1,0,0,0 0,1,0,0 0,0,1,0*/ #include<cstdio> #include<cstring> int L,M,ans; int init[4] = {2,4,6,9}; struct Matrix{ int mat[4][4]; Matrix operator * (const Matrix rhs) const{ Matrix temp; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ temp.mat[i][j] = 0; for(int k=0;k<4;k++) { temp.mat[i][j] += this->mat[i][k]*rhs.mat[k][j]%M; temp.mat[i][j] %= M; } } } return temp; } }; Matrix mt,ret; int main() { while(~scanf("%d%d",&L,&M)) { memset(mt.mat,0,sizeof(mt.mat)); memset(ret.mat,0,sizeof(ret.mat)); for(int i=0;i<4;i++)mt.mat[0][i] = i==1?0:1; for(int i=0;i<3;i++)mt.mat[i+1][i] = 1; for(int i=0;i<4;i++)ret.mat[i][i] = 1; ans = 0; if(L<=4){ printf("%d\n",L==0?0:init[L-1]%M); }else{ L = L-4; for(int i=0;i<4;i++) ret.mat[i][i] = 1; while(L) { if(L&1)ret = ret*mt; mt = mt*mt; L>>=1; } for(int i =0;i<4;i++){ ans = (ans+ret.mat[0][i]*init[3-i]%M)%M; } printf("%d\n",ans); } } return 0; } //超时代码 /* #include<cstdio> #define MAXN 1000010 int L,M; int F[MAXN]; int main() { F[1] = 2; F[2] = 4; F[3] = 6; F[4] = 9; while(~scanf("%d%d",&L,&M)) { for(int i=5;i<=1000000;i++) F[i] = (F[i-1]+F[i-3]+F[i-4])%M; printf("%d\n",F[L]%M); } }*/
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
HDU最全ac代码
hdu 1166线段树代码
hdu动态规划算法集锦
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
hdu题目分类
HDU图论题目分类
自己做的HDU ACM已经AC的题目
hdu 1005.比较简单的一道题,有兴趣的可以看看。