矩阵快速幂

设F(N)为字符串为N的时候，符合条件的子字符串数

以字符串最后一个字符为分界点，最后一个字符为m的时候，前N-1个字符没有限制，即为F(N-1);

当最后一个字符串为f的时候，就必须去除最后3个字符是fmf和fff的情况，此时最后3个字符可能为mmf和mff；

当后3个字符为mm时，前N-3个字符没有限制，即F(N-3);

但是当最后3个字符为mff时，后四个字符必须为mmff时前N-4个字符无限制，即为F(N-1);

 

所以递推为F(N)=F(N-1)+F(N-3)+F(N-4);

F0=0 F1=2 F2=4 F3=6 F4=9

1011  F(N-1)　　F(N)

1000　F(N-2)　=F(N-1)

0100　F(N-3)　　F(N-2)

0010　F(N-4)　　F(N-3)

 

 

 

#include <iostream>

#include <string.h>

using namespace std;

int n,m;

struct M{　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//矩阵结构体

    int t[4][4];

    M(){

        memset(t,0,sizeof(t));

    }

    void init(){

        t[0][0]=t[0][2]=t[0][3]=t[1][0]=t[2][1]=t[3][2]=1;

    }

    void E(){　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//单位矩阵

        for(int i=0;i<4;i++){

            t[i][i]=1;

        }

    }

};

M multiply(M a,M b){　　　　　　　　　　　　　　　　　　　　　　　　　　//矩阵乘法

    M c;

    for(int i=0;i<4;i++){

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

            for(int k=0;k<4;k++){

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

            }

        }

    }

    return c;

}

M powM(M a,int k){　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//矩阵的幂运算

    M tem;

    tem.E();

    while(k){

        if(k&1)tem=multiply(a,tem);

        a=multiply(a,a);

        k>>=1;

    }

    return tem;

}

int main(){

    int t;

    M a,b,c;

    a.t[0][0]=9;

    a.t[1][0]=6;

    a.t[2][0]=4;

    a.t[3][0]=2;

    b.init();

    while(cin>>n>>m){

        if(n<5){

            if(n==0)cout<<"0"<<endl;

            else cout<<a.t[4-n][0]%m<<endl;

        }

        else {

            c=powM(b,n-4);

            c=multiply(c,a);

            cout<<c.t[0][0]%m<<endl;

        }

    }

    return 0;

}