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 3 8 4 7 4 8
Sample Output 6 2 1分析： 題目要求不含101 和111 的串設f[n]為長度為n串符合條件的個數則很明顯在長度為（n-1）并且符合條件的串后面加上一個0一定符合如果在長度為n-1的串后面加上一個1的話我們得考慮n-1的串結尾的元素如果是00的話我們可以看做是長度為n-3的串加上100?如果是10的話我們可以看做長度為n-4的串加上1100因此f[n]=f[n-1]+f[n-3]+f[n-4];方法一：直接遞推（耗時多可能超時）#include <iostream> #include <cstdio> using namespace std; int n,M; int main() {int n,m;int a[4];while(~scanf("%d%d",&n,&M)){a[0]=1;a[1]=2;a[2]=4;a[3]=6;for(int i=4;i<=n;i++){a[4]=(a[0]+a[1]+a[3])%M;a[0]=a[1];a[1]=a[2];a[2]=a[3];a[3]=a[4];}if(n>=4)cout<<a[4]%M<<endl;elsecout<<a[n]%M<<endl;}return 0; }
方法二：（矩陣加速）#include <iostream> #include <cstdio> using namespace std; int n,M; struct matrax {int m[4][4]; }; matrax A={1,0,1,1,1,0,0,0,0,1,0,0,0,0,1,0 }; matrax E; void init() {for(int i=0;i<4;i++)for(int j=0;j<4;j++)E.m[i][j]=(i==j); } matrax multi(matrax a,matrax b) {matrax c;for(int i=0;i<4;i++){for(int j=0;j<4;j++){c.m[i][j]=0;for(int k=0;k<4;k++)c.m[i][j]+=a.m[i][k]*b.m[k][j]%M;c.m[i][j]%=M;}}return c; } matrax power(matrax A,int k) {matrax ans=E,p=A;while(k){if(k&1){ans=multi(ans,p);k--;}k>>=1;p=multi(p,p);}return ans; } int main() {init();int a[4]={1,2,4,6};while(cin>>n>>M){matrax ans=power(A,n-3);int x=0;for(int i=0;i<4;i++)x+=(ans.m[0][i]*a[4-i-1])%M;/*for(int i=0;i<4;i++){for(int j=0;j<4;j++)cout<<ans.m[i][j]<<" ";cout<<endl;}*/cout<<x%M<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的HDU2604Queuing的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。