矩阵快速幂
设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;
}