2014
02-10

# Queuing

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.

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

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

3 8
4 7
4 8

6
2
1

1 根据题目的意思，我们可以求出F[0] = 0 , F[1] = 2 , F[2] = 4 , F[3] = 6 , F[4] = 9 , F[5] = 15

2 那么根据上面前5项我们可以求出n >= 5的时候 F[n] = F[n-1]+F[n-3]+F[n-4]

那么我们就可以构造出矩阵

| 1 0 1 1 |     | F[n-1] |    | F[n] |

| 1 0 0 0 |  *  | F[n-2] | = | F[n-1] |

| 0 1 0 0 |     | F[n-3] |    | F[n-2] |

| 0 0 1 0 |     | F[n-4] |    | F[n-3] |

/************************************************
* By: chenguolin                               *
* Date: 2013-08-23                             *
***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int N = 4;

int n , MOD;
struct Matrix{
int64 mat[N][N];
Matrix operator*(const Matrix& m)const{
Matrix tmp;
for(int i = 0 ; i < N ; i++){
for(int j = 0 ; j < N ; j++){
tmp.mat[i][j] = 0;
for(int k = 0 ; k < N ; k++){
tmp.mat[i][j] += mat[i][k]*m.mat[k][j]%MOD;
tmp.mat[i][j] %= MOD;
}
}
}
return tmp;
}
};

int Pow(Matrix &m){
if(n <= 3)
return (2*n)%MOD;
if(n == 4)
return 9%MOD;
n -= 4;
Matrix ans;
memset(ans.mat , 0 , sizeof(ans.mat));
for(int i = 0 ; i < N ; i++)
ans.mat[i][i] = 1;
while(n){
if(n&1)
ans = ans*m;
n >>= 1;
m = m*m;
}

int sum = 0;
sum += ans.mat[0][0]*9%MOD;
sum += ans.mat[0][1]*6%MOD;
sum += ans.mat[0][2]*4%MOD;
sum += ans.mat[0][3]*2%MOD;
return sum%MOD;
}

int main(){
Matrix m;
while(scanf("%d%d" , &n , &MOD) != EOF){
memset(m.mat , 0 , sizeof(m.mat));
m.mat[0][0] = m.mat[0][2] = m.mat[0][3] = 1;
m.mat[1][0] = m.mat[2][1] = m.mat[3][2] = 1;
printf("%d\n" , Pow(m));
}
return 0;
}

1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), [email protected]
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}