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

 

Author

WhereIsHeroFrom

 

Source

 

Recommend

lcy

 

（設f(n)為字符串為n時符合條件的字符串個數。

以字符串最後一個字符為分界點，當最後一個字符為m時前n-1個字符沒有限制，即為f(n-1)；

當最後一個字符為f時就必須去除最後3個字符是fmf和fff的情況，此時最後三個字符可能為mmf和mff，

當後三個字符為mmf時，前n-3個字符沒有限制，即為f(n-3)；

但是當後三個自負為mff時，後四個字符必須為mmff時前n-4個字符無限制，即為f(n-4)。

這樣就討論完了字符串的構成情況了，得出結論為：f(n) = f(n-1) + f(n-3) + f(n-4).   ）

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,mod;

struct Matrix{

    int arr[][];

};

Matrix unit,init;

Matrix Mul(Matrix a,Matrix b){

    Matrix c;

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

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

            c.arr[i][j]=;

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

                c.arr[i][j]=(c.arr[i][j]+a.arr[i][k]*b.arr[k][j]%mod)%mod;

            c.arr[i][j]%=mod;

        }

    return c;

}

Matrix Pow(Matrix a,Matrix b,int k){

    while(k){

        if(k&){

            b=Mul(b,a);

        }

        a=Mul(a,a);

        k>>=;

    }

    return b;

}

void Init(){

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

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

            init.arr[i][j]=;

            unit.arr[i][j]=;

        }

    unit.arr[][]=,   unit.arr[][]=,   unit.arr[][]=,   unit.arr[][]=;

    init.arr[][]=,   init.arr[][]=,   init.arr[][]=,   init.arr[][]=,

    init.arr[][]=,   init.arr[][]=;

}

int main(){

    //freopen("input.txt","r",stdin);

    Init();

    while(~scanf("%d%d",&n,&mod)){

        if(n<=){

            if(n==)

                printf("");

            else if(n==)

                printf("%d\n",%mod);

            else if(n==)

                printf("%d\n",%mod);

            else if(n==)

                printf("%d\n",%mod);

            else if(n==)

                printf("%d\n",%mod);

            continue;

        }

        Matrix res=Pow(init,unit,n-);

        printf("%d\n",res.arr[][]%mod);

    }

    return ;

}