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

 

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

typedef long long ll;

#define mod(x) ((x)%MOD)

ll MOD;

//2 4 6 9

struct mat

{

    int m[maxn][maxn];

    mat(){

        memset(m,,sizeof(m));

    }

}unit;

mat operator*(mat a,mat b)

{

    mat ret;

    ll x,n=;

    for(int i=;i<n;i++)

    {

        for(int j=;j<n;j++)

        {

            x=;

            for(int k=;k<n;k++)

            {

                x+=mod((ll)a.m[i][k]*b.m[k][j]);

            }

            ret.m[i][j]=mod(x);

        }

    }

    return ret;

}

void iint()

{

    for(int i=;i<maxn;i++)

    {

        unit.m[i][i]=;

    }

    return ;

}

mat pow1(mat a,ll n)

{

    mat ret=unit;

    while(n)

    {

        if(n&)

        {

            n--;ret=ret*a;

        }

        n>>=;

        a=a*a;

    }

    return ret;

}

int main()

{

    ll k;

    mat b;

    b.m[][]=; b.m[][]=; b.m[][]=;  b.m[][]=;

    //f(1)对于f(n)来说是f(n-4)，这四项写反，查错了好久，哭

    while(cin>>k>>MOD)

    {

        if(k<=) {  cout<<b.m[-k][]%MOD<<endl;continue;}

        iint(); //构建单位阵

        mat a;

        a.m[][]=a.m[][]=a.m[][]=a.m[][]=a.m[][]=a.m[][]=;

        //a.m[0][1]=a.m[1][1]=a.m[1][2]=a.m[1][3]=a.m[2][0]=a.m[2][2]=a.m[2][3]=a.m[3][0]=a.m[3][1]=a.m[3][3]=0;

        a=pow1(a,k-); //进行k-4次快速幂即可

        a=a*b;

        /*for(int i=0;i<4;i++)

        { //这是查看矩阵的= =

            for(int j=0;j<4;j++)

            {

                if(j+1==4) cout<<a.m[i][j]<<endl;

                else cout<<a.m[i][j]<<" ";

            }

        }*/

        cout<<mod(a.m[][])<<endl;

    }

    return ;

}